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
| # *-coding:Utf-8 -*
class vertex:
def __init__(self, name, value):
self.name = name
self.buddies = dict()
self.value = value
def __str__(self):
return str(self.name)
class Graph:
def __init__(self, name, vertices):
self.vertices = vertices
self.name = name
def Dijkstra(G, source):
sPaths = [(float('inf'), vertex) for vertex in G.vertices]
sPaths[source.value] = (0, source)
pivot = source
papas = [None]*len(G.vertices)
done = []
while len(done) != (len(G.vertices)-1):
for buddy in pivot.buddies.keys():
if(sPaths[buddy.value][0] > sPaths[pivot.value][0] + pivot.buddies[buddy]):
sPaths[buddy.value] = (sPaths[pivot.value][0] + pivot.buddies[buddy], sPaths[buddy.value][1])
papas[buddy.value] = pivot
done.append(pivot)
for path in sPaths:
if path[0] == min(sPaths, key=lambda e: e[0])[0]:
pivot = path[1]
for path in sPaths:
print("distance de "+str(source)+"à "+ str(path[1])+"= "+path[0]+"\n")
A = vertex("A", 0)
B = vertex("B", 1)
C = vertex("C", 2)
D = vertex("D", 3)
E = vertex("E", 4)
S = vertex("S", 5)
E.buddies = {A:3, B:1}
A.buddies = {E:3, B:1, C:3}
B.buddies = {E:1, A:1, C:3, D:5}
C.buddies = {A:3, B:3, D:1, S:3}
D.buddies = {B:5, C:1, S:1}
G = Graph("G", [A, B, C, D, E, S])
Dijkstra(G,E) |
Partager