-
Notifications
You must be signed in to change notification settings - Fork 0
/
Dijkstra.py
71 lines (50 loc) · 1.31 KB
/
Dijkstra.py
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
def initial_graph() :
return {
'A': {'B':9, 'C':4, 'D':2},
'B': {'A':9, 'E':5},
'C': {'A':4, 'F':15},
'D': {'A':2, 'F':7},
'E': {'B':5, 'J':7},
'F': {'C':15, 'D':7, 'K':3, 'G':9},
'G': {'F':9, 'I':4},
'H': {'J':2},
'I': {'G':4, 'J':7},
'J': {'H':2, 'I':7},
'K': {'F':3}
}
print(initial_graph())
initial = 'B'
path = {}
adj_node = {}
queue = []
graph = initial_graph()
for node in graph:
path[node] = float("inf")
adj_node[node] = None
queue.append(node)
path[initial] = 0
while queue:
# find min distance which wasn't marked as current
key_min = queue[0]
min_val = path[key_min]
for n in range(1, len(queue)):
if path[queue[n]] < min_val:
key_min = queue[n]
min_val = path[key_min]
cur = key_min
queue.remove(cur)
print(cur)
for i in graph[cur]:
alternate = graph[cur][i] + path[cur]
if path[i] > alternate:
path[i] = alternate
adj_node[i] = cur
x = 'I'
print('The path between B to I')
print(x, end = '<-')
while True:
x = adj_node[x]
if x is None:
print("")
break
print(x, end='<-')