dij
123456789101112131415161718192021222324252627
import heapq
def dij(v,adj,src):
dist=[0]*v
q=[]
heapq.heappush(q,[0,src])
dist[src]=0
while q:
u=heapq.heappop(q)[1]
for v, w in adj[u]:
if dist[v] > dist[u] + w:
# Updating distance of v
dist[v] = dist[u] + w
heapq.heappush(pq, [dist[v], v])
return dist
V = 5
src = 0
# edge list format: {u, v, weight}
adj = [
[(1, 4), (2, 8)], # Node 0 → (1, weight 4), (2, weight 8)
[(0, 4), (4, 6)], # Node 1 → (0, 4), (4, 6)
[(0, 8), (3, 2)], # Node 2 → (0, 8), (3, 2)
[(2, 2), (4, 10)], # Node 3 → (2, 2), (4, 10)
[(1, 6), (3, 10)] # Node 4 → (1, 6), (3, 10)
]
dij(V, adj, src)
Python
INFO