-
Notifications
You must be signed in to change notification settings - Fork 0
/
dijkstra.py
39 lines (32 loc) · 981 Bytes
/
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
import heapq
def dijkstra(G,start):
INF = 999999999
dis = dict((key,INF) for key in G)
dis[start] = 0
vis = dict((key,False) for key in G)
pq = []
heapq.heappush(pq,[dis[start],start])
path = dict((key,[start]) for key in G)
while len(pq)>0:
v_dis,v = heapq.heappop(pq)
if vis[v] == True:
continue
vis[v] = True
p = path[v].copy()
for node in G[v]:
new_dis = dis[v] + float(G[v][node])
if new_dis < dis[node] and (not vis[node]):
dis[node] = new_dis
heapq.heappush(pq,[dis[node],node])
temp = p.copy()
temp.append(node)
path[node] = temp
return dis,path
V, A = list(map(int, input().split()))
G= {}
for i in range(1, V+1):
G[i] = {i:0}
for i in range(A):
ini, fim, peso = list(map(int, input().split()))
G[ini].update({fim:peso})
distance,path = dijkstra(G,1)