[Déplacé depuis http://www.developpez.net/forums/d85...lgo-dijkstra/]

ben moi aussi je doit implémenté dijkstra en plus avec python , j'ai fais une matrice d'incidence des poids des arêtes , une matrice de voisinage par rapport a tout les sommet mais voila , le féte que mon graphe soit non orienté me fausse l'idée de l'algorithme en lui méme , j'arrive pas a trouvé une idée logique pour la comparaison , je vous mes mon programme svp aidé moi c urgent



Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
# ==============================================================================
from random import randrange as rr
from random import *
from copy import *
from math import *
from time import time
 
#===================================================================================
#structuration du graphe (circuit férovier )
#===================================================================================
def struct_graphe():
    donnees = open('kenzam1.txt','r')
    nom = donnees.read()
    ligne = nom.split('\n')
    colonne = ligne[1].split()
    nbtrain = int(colonne[0])
    j=1
    listedepart = []
 
    for i in range(3,14):
        colonne = ligne[i].split()
        listedepart.append (int(colonne[0]))
 
    listearrivee = []
 
    for i in range(3,14):
        colonne = ligne[i].split()
        listearrivee.append( int(colonne[1]))
 
    listearetes_poid = []
 
    for i in range(15,28):
        colonne = ligne[i].split()
        listearetes_poid.append ((int(colonne[0]),int(colonne[1]),(int(colonne[2]))))
 
    train_depart_arrivee = []
 
    for i in range(29,40):
 
        colonne = ligne[i].split()
        train_depart_arrivee.append ([(j),int(colonne[0]),int(colonne[1])])
        j=j+1
 
 
    return nbtrain,listedepart,listearrivee,listearetes_poid,train_depart_arrivee
 
 
 
 
NB_train,D,A,AR_P,Q=struct_graphe()
print NB_train,'\n',D,'\n',A,'\n',AR_P,'\n',Q
 
liste_sommet=[1,2,3,4,5,6,7,8,9,10,11,12,13]
n=(len(liste_sommet))
m=len(AR_P)
L=[[0 for j in xrange(0,n)] for i in  xrange(0,n)]
 
#print L
#======================================================================================
#Matrice d'adjacence de notre  graphe (avec enumération des poids  )
#======================================================================================
 
def matrice_adjcence_poid(liste_sommet,AR_P,L):
    for x in range (0,len(liste_sommet)):
     for i in range (0,len(AR_P)):
        for j in range (0,len(AR_P[i])):
            if liste_sommet [x]== AR_P[i][0]:
              t=(AR_P[i][0]-1)  
              z=(AR_P[i][1]-1)
              L[t][z]=AR_P[i][2]
              L[z][t]=AR_P[i][2]
 
    return L
 
Adjacence=matrice_adjcence_poid(liste_sommet,AR_P,L)
print Adjacence
#=======================================================================================
#matrice définissant le voisinage de chaque sommet dans le graphe (sommet représentant arrét)
#=======================================================================================
 
def voisinage (L):
    v=[]
    for i in range (0,len(L)):
        sommet=[]
        for j in range (0,len(L[i])):
 
            if L[i][j]>0:
                sommet.append(j+1)
 
        v.append(sommet)
 
    return v
 
V=voisinage(L)
print V
 
#==============================================================================
#initialisation des variable Utile pour l'algorithme de Dijkstra
#==============================================================================
 
def init(First,Last):
    liste_precd=[]
    liste_poid_chemin=[0 for i in xrange(n)]
    depart=First
    arrivee=Last
    return liste_precd,liste_poid_chemin,depart,arrivee
 
#==============================================================================
# initialisation de l'algorithme de Dijkstra
#==============================================================================
 
def init_algo(n ,liste_poid_chemin,depart):
    liste_poid_chemin[depart-1]=0
    for i in range (n):
     if (i!= (depart-1)):
        liste_poid_chemin[i]=10000000
    return liste_poid_chemin
 
 
#================================================================================
#Fonction qui compare entre poid des arrétes et choisit le min (coprs algo)
#================================================================================
 
def compare (V,L,depart,arrivee,liste_precd,liste_poid_chemin):
    voisin_imme=V[depart-1]
    poid_imme=L[depart-1]
    for j in range (len(voisin_imme)):
         c = liste_poid_chemin[depart-1]+ poid_imme[voisin_imme[j]-1]
         if (liste_poid_chemin[j])>c :
             liste_poid_chemin[j]=c
             liste_precd+=[depart]
             x=(voisin_imme[j]-1)
             #compare(V,L,x,arrivee,liste_precd,liste_poid_chemin)
    return liste_precd,liste_poid_chemin
 
#================================================================================
#Algortihme de Dijkstra
#================================================================================
 
def dijkstra(First,Last):
            liste_precd,liste_poid_chemin,depart,arrivee=init(First,Last)
            liste_poid_chemin=init_algo(n ,liste_poid_chemin,depart)
            LPE,LPO=compare(V,L,depart,arrivee,liste_precd,liste_poid_chemin)
            return LPE,LPO
 
 
 
 
#=================================================================================
# ___________________________________main______________________________________
#==================================================================================        
 
if __name__ == "__main__":
    for x in range(0,len (Q)):
        First= Q[x][1]
        Last= Q[x][2]
        print First
        print Last
        A,B=dijkstra(First,Last)
        print A
        print B