Bonjour!

Dans le cadre de mon projet d'ISN, je réalise avec trois de mes mais un logiciel qui permet de trouver le plus court chemin dans un graphe en t'utilisant l'algorithme de Dijkstra. Je m'occupe de la ^partie algorithme, et les deux autres de l'interface utilisateur de la fenêtre de rendu ( censée afficher le graphe ). Mais je bloque à la fin de mon algorithme. Pour le réaliser, je m'aide de ce site : http://www.apprendre-en-ligne.net/graphes/dijkstra/algorithme.html

Pour l'instant, voilà mon code (en prenant en compte que la matrice sera généra par l'utilisateur, ici, ce n'est qu'une matrice de test qui correspond à celle du site ):

### Initialisation ###

mat = [['0','15','0','10','4','0','0','0','0','0']
         ,['0','0','3','3','0','0','0','0','0','0']
         ,['0','0','0','2','7','0','0','0','0','0']
         ,['0','0','0','0','5','0','0','0','0','0']
         ,['0','0','0','0','0','0','0','0','0','0']
         ,['0','0','0','0','0','0','0','0','0','0']
         ,['0','0','0','0','0','0','0','0','0','0']
         ,['0','0','0','0','0','0','0','0','0','0']
         ,['0','0','0','0','0','0','0','0','0','0']
         ,['0','0','0','0','0','0','0','0','0','0']]
		 
S = [1]
T = []
P = []

L = []
####### -- T -- ########
i=1
while i<len(mat[1]):
		T.append(int(i+1))
		i = i+1
####### -- P ET L -- ########
i=0
while i<len(mat[1]):
		P.append(0)
		L.append(9999)
		i = i+1
###############
i=0
while i<len(mat[0]):
    if int(mat[0][i]) != 0:        
        if int(mat[0][i])<int(L[i]):
            L[i]= int(mat[0][i])
    i = i+1
print ('S =', S)
print ('L =', L)
print ('T =', T)
print ('P =', P)
    
################# BOUCLE PRINCIPALE #####################

while len(T) > 0:
    k = min(L)
    i = L.index(int(k))
    print ('I =', i)
    print ('K =', k)
    T.remove(i)
    #L.remove(k+1)
    S.append(i+1)
    print ('T = ', T)
    print('S = ', S)
    print ('L =', L)
    
    # Vérifier plus court chemin
    j=0
    while j<len(mat[i-1]):
        if int(mat[i-1][j]) != 0:   # j = successeur de i     
            if int(L[j])>int(L[i]) + int(mat[i][j]):
                L[j]= int(L(i-1)) + int(mat[i-1][j])
                P[j] = i
                print ('P =', P)
        j = j+1
    print ('----- Itération fini -----')

Mais j'ai toujours une erreur, comment faire pour que mon algorithme marche et me retourne le chemin le plus court qui devrait être stocké dans la liste P ?

Salut,

Ton code n'est pas très clair.

Déjà tu devrais convertir dès le départ ta matrice en liste d'entiers pour ne pas traîner des chaînes de caractères.

Ensuite, tu pourrais réduire toute cette partie

S = [1]
T = []
P = []
L = []

-- T --

i=1 while i<len(mat[1]):

    T.append(int(i+1))
    i = i+1

-- P ET L --

i=0 while i<len(mat[1]):

    P.append(0)
    L.append(9999)
    i = i+1

i=0 while i<len(mat[0]):

if int(mat[0][i]) != 0:       
    if int(mat[0][i])<int(L[i]):
        L[i]= int(mat[0][i])
i = i+1

Avec :

S = [1]
P = [0] * len(mat[1])
T = list(range(2, len(mat[1])+1))
L = [x if x else 9999 for x in mat[0]]

Pour la « boucle principale », je n'ai pas le temps de m'y pencher mais revois l'algorithme, à première vue tu l'appliques mal et confonds les indices et les listes. La première erreur vient du fait que tu essayes de retirer de T un élément de L alors que tu devrais sélectionner le minimum de T et non de L. Aussi, l'initialisation me semble fausse par rapport à ce que tu souhaites appliquer (et il y a sans doute plus judicieux que 9999 comme valeur par défaut).

-
Edité par Anonyme 14 mai 2013 à 20:10:17

Pourtant, l'algo a été vu par mon prof et il m'a dit de faire comme sa pour la boucle principale .. Enfin, je vais revoir tous sa comme tu m'a dit, et je te dirais ce qu'il en est

Ah et merci pour l'aide du début, c'est vrai que sa fait tout de suite beaucoup moins de ligne

T = [x for x in range(2, len(mat[1]) + 1)]

Sérieusement ?

-
Edité par BananeFraise 14 mai 2013 à 19:51:22

En effet, c'est corrigé.