Bonsoir, je poste ici après des heures de recherches par moi-même, je vous explique mon problème :

Pour un projet de python, je dois créer un algorithme qui prend en entrée une matrice d'adjacence, un point de départ, un point d'arrivée et qui multiplie la matrice d'adjacence par elle même tant que la case point d'arrivée/point de départ contient un 0. L'algorithme doit retourner le nombre d'itérations de l'algorithme.

Mon problème est que mon algo rentre dans une boucle infinie, sans raison, et ce, uniquement quand ma matrice est grande.

Voici le code : 

def multiplicationMatrices(mat1, n, m, mat2, p):

    mat3 = []

    for i in range(n):

        mat3.append([])

        for j in range(p):

            element = 0

            for k in range(m):

                element = element + (mat1[i][k] * mat2[k][j])

            mat3[i].append(element)

    #for y in range(len(mat3)):

        #print(mat3[y])

    return mat3

def pptMaj(matrice,i,j):

    n=1

    if i == j:

        return 0

    while matrice[i][j] == 0:

        if n == 5 :

            for y in range(len(matrice)):

                print(matrice[y])

            break

        matrice = multiplicationMatrice(matrice,len(matrice),len(matrice[0]),matrice,len(matrice[0])

        n = n + 1

        print(n)

    return n

Ligne3BIS = ["Porte Des Lilas","Saint-Fargeau","Pelleport","Gambetta"]

Ligne7BIS = ["Louis Blanc","Jaures","Bolivar","Buttes Chaumont","Botzaris","Place des fetes/Danube","Pre-Saint-Gervais"]

Ligne11 = ["Chatelet","Hotel De Ville","Rambuteau","Arts et Metiers","Republique","Goncourt","Belleville","Pyrenees","Jourdain","Place Des Fetes","Telegraphe","Porte des Lilas","Mairie des Lilas"]

Ligne14 = ["Saint-Lazare","Madeleine","Pyramides","Chatelet","Gare de Lyon","Bercy","Cour Saint-Emilion","Bibliotheque Francois Mitterand","Olympiades"]

DictionnaireNstationsNomStations = {"Porte Des Lilas":0,"Saint-Fargeau":1,"Pelleport":2,"Gambetta":3,"Louis Blanc":4,"Jaures":5,"Bolivar":6,"Buttes Chaumont":7,"Botzaris":8,"Place Des Fetes":9,"Danube":9,"Pre-Saint-Gervais":10,"Chatelet":11,"Hotel De Ville":12,"Rambuteau":13,"Arts et Metiers":14,"Republique":15,"Goncourt":16,"Belleville":17,"Pyrenees":18,"Jourdain":19,"Telegraphe":20,"Mairie Des Lilas":21,"Saint-Lazare":22,"Madeleine":23,"Pyramides":24,"Gare de Lyon":25,"Bercy":26,"Cour Saint-Emilion":27,"Bibliotheque Francois Mitterand":28,"Olympiades":29}

MatriceAdjacence = [[0 for j in range(0,30)] for i in range(0,30)]

MatriceAdjacence[0][1] = 1

MatriceAdjacence[0][20] = 1

MatriceAdjacence[0][21] = 1

MatriceAdjacence[1][0] = 1

MatriceAdjacence[1][2] = 1

MatriceAdjacence[2][1] = 1

MatriceAdjacence[2][3] = 1

MatriceAdjacence[3][2] = 1

MatriceAdjacence[4][5] = 1

MatriceAdjacence[5][4] = 1

MatriceAdjacence[5][6] = 1

MatriceAdjacence[6][5] = 1

MatriceAdjacence[6][7] = 1

MatriceAdjacence[7][6] = 1

MatriceAdjacence[7][8] = 1

MatriceAdjacence[8][7] = 1

MatriceAdjacence[8][9] = 1

MatriceAdjacence[9][8] = 1

MatriceAdjacence[9][10] = 1

MatriceAdjacence[9][19] = 1

MatriceAdjacence[9][20] = 1

MatriceAdjacence[10][9] = 1

MatriceAdjacence[11][12] = 1

MatriceAdjacence[11][24] = 1

MatriceAdjacence[11][25] = 1

MatriceAdjacence[12][11] = 1

MatriceAdjacence[12][13] = 1

MatriceAdjacence[13][12] = 1

MatriceAdjacence[13][14] = 1

MatriceAdjacence[14][13] = 1

MatriceAdjacence[14][15] = 1

MatriceAdjacence[15][14] = 1

MatriceAdjacence[15][16] = 1

MatriceAdjacence[16][15] = 1

MatriceAdjacence[16][17] = 1

MatriceAdjacence[17][16] = 1

MatriceAdjacence[17][18] = 1

MatriceAdjacence[18][17] = 1

MatriceAdjacence[18][19] = 1

MatriceAdjacence[19][9] = 1

MatriceAdjacence[19][18] = 1

MatriceAdjacence[20][0] = 1

MatriceAdjacence[20][9] = 1

MatriceAdjacence[21][0] = 1

MatriceAdjacence[22][23] = 1

MatriceAdjacence[23][22] = 1

MatriceAdjacence[23][24] = 1

MatriceAdjacence[24][11] = 1

MatriceAdjacence[24][23] = 1

MatriceAdjacence[25][11] = 1

MatriceAdjacence[25][26] = 1

MatriceAdjacence[26][25] = 1

MatriceAdjacence[26][27] = 1

MatriceAdjacence[27][26] = 1

MatriceAdjacence[27][28] = 1

MatriceAdjacence[28][27] = 1

MatriceAdjacence[28][29] = 1

MatriceAdjacence[29][28] = 1

matriceTest = [[0,1,0,0,1,0],[1,0,1,0,1,0],[0,1,0,1,0,0],[0,0,1,0,1,1],[1,1,0,1,0,0],[0,0,0,1,0,0]]

print("Ligne 3 BIS : ")

print(Ligne3BIS)

print("\n")

print("Ligne 7 BIS : ")

print(Ligne7BIS)

print("\n")

print("Ligne 11 : ")

print(Ligne11)

print("\n")

print("Ligne 14 : ")

print(Ligne14)

print("\n")

for i in range(len(MatriceAdjacence)):

    print(MatriceAdjacence[i])

Merci d'avance pour votre aide

Balises de code stp. Sinon tu risques de ne pas trouver beaucoup d'aide...

-
Edité par Dan737 1 décembre 2015 à 9:27:16

• OMG UTILISEZ  CES BALISES  CODE C'EST ILLISIBLE
• Parenthèse non fermée (dans fonction pptMaj(), 3 lignes avant le return)
• fonction multiplicationMatrice n'existe pas (dans fonction pptMaj())
• Utilisation de break déconseillée m'enfin bref
• Si  ton script cycle c'est probablement pas sans raison comme tu laisse l'entendre
• Met des 'docstring' dans tes fonctions sinon on comprends pas ce qu'elles font
• Information superflue (inutilisées en tout cas) pour ce que tu nous demande m'enfin bref (fonction pptMaj, 'matriceTest', fonction multiplicationMatrices) 
• range(0,30) == range(30)
• ET ENFIN: ton code ne peut pas cycler vu que ton main ne fait rien a part afficher la matrice ligne par ligne et que ta matrice n'est de toute évidence pas infinie