Algorithme Dijkstra

Version imprimable

Algorithme Dijkstra

[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
:cry: :cry: :cry:

Code:

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

22/04/2012, 15h18
pacificator

Bonjour,

peux-tu donné un exemple des données que tu traites en entrée et de ce que tu veux obtenir?

Merci.

Bonjour,

Je ne vois pas pourquoi le fait que le graphe soit non orienté te pose un problème pour cet algorithme. Il suffit de le considérer comme un graphe orienté avec les arêtes présentes dans les deux directions...

J'ai beaucoup de mal à comprendre ton code, mais si ça peut t'inspirer, voici une implémentation simple mais assez efficace de Dijkstra que j'ai écrite il y a quelques temps:

Code:

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
from collections import defaultdict, OrderedDict
from heapq import *
 
def ugraph(*edges):
    G = defaultdict(dict)
    for src,dst,cost in edges:
        G[src][dst] = cost
        G[dst][src] = cost
    return G
 
def dijkstra(G, v):
    candidates = [(0,v,None)]   # (total cost, current node, previous node)
    result = OrderedDict()
    while candidates:
        cost,curr,prev = heappop(candidates)
        if curr in result: continue
        result[curr] = (prev, cost)
        for next in G[curr].keys():
            if next not in result:
                heappush(candidates, (cost + G[curr][next],next,curr))
    return result
 
if __name__ == '__main__':
    net = ugraph(
        ('A','B',5) , ('A','C',5) , ('A','D',20),
        ('B','C',5) , ('B','E',10),
        ('C','D',10), ('C','F',8) , ('C','G',10), ('C','H',6),
        ('D','F',6) ,
        ('E','H',7) ,
        ('F','K',7) ,
        ('G','H',6) , ('G','J',8),
        ('H','I',20),
        ('I','J',5) ,
        ('J','K',6) ,
        ('K','L',20), ('K','M',5),
        ('L','M',5)
        )
 
    path = dijkstra(net, 'A')
    print(path)

30/05/2014, 12h03
Invité

Merci pour l'implémentation de Dijkstra + question

Bonjour,

Merci pour ce petit programme. Le post date de 2007 mais j'espère avoir une réponse.
Je débute en Python/Dijkstra. Quand j'execute ton programme, j'obtiens:

Code:

OrderedDict([('A', (None, 0)), ('B', ('A', 5)), ('C', ('A', 5)), ('H', ('C', 11)), ('F', ('C', 13)), ('D', ('C', 15)), ('E', ('B', 15)), ('G', ('C', 15)), ('K', ('F', 20)), ('J', ('G', 23)), ('M', ('K', 25)), ('I', ('J', 28)), ('L', ('M', 30))])

Quel est donc le chemin le plus court? Son poids?
Dans le code, où rentres-tu le point de départ? Le point d'arrivée?

Merci d'avance
08/06/2014, 09h54
dividee

C'est pas tout récent comme discussion, mais elle date de 2012, quand-même pas 2007 ;)

Citation:

Envoyé par mp0777236

Quel est donc le chemin le plus court? Son poids?
Dans le code, où rentres-tu le point de départ? Le point d'arrivée?

Le point de départ, c'est celui qui est passé en argument à la fonction dijkstra, c'est-à-dire le sommet "A".
L'algorithme de dijkstra calcule le plus court chemin de ce sommet de départ vers tous les autres sommets du graphe, il n'y a donc pas un seul point d'arrivée.
Ou alternativement, lorsque le graphe est non-orienté comme dans l'exemple, il calcule le plus court chemin de tous les sommets du graphe vers un sommet d'arrivée donné (A).

L'affichage du résultat n'est pas très travaillé mais contient les infos nécessaires: à chaque sommet du graphe, il associe le sommet précédent sur le chemin le plus court depuis A et le coût total de ce chemin.
Pour retrouver le chemin complet, pour un sommet d'arrivée donné, il faut partir de celui-ci et remonter jusqu'à la source.
Par exemple, le sommet qui précède K est F, celui qui précède F est C, celui qui précède C est A. Aucun sommet ne précède A vu que c'est la source (indiqué par le None). Le chemin entre A et K est donc A-C-F-K et son coût est de 20.

J'avais utilisé un OrderedDict de façon à ce que les sommets soient affichés dans l'ordre de découverte par l'algorithme, c'est plus facile à suivre si on exécute l'algorithme soi-même pour vérifier. Ca permet notamment de voir que les sommets les plus proches sont bien découverts en premier.
10/06/2014, 00h15
Invité

Ah oui j'ai mal lu ;)

Merci pour les explications en tout cas!