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)
import heapq
def dij(v, adj, src):
dist = [float('inf')] * v
dist[src] = 0
q = []
heapq.heappush(q, [0, src])
while q:
u = heapq.heappop(q)[1]
for neighbor, weight in adj[u]:
if dist[neighbor] > dist[u] + weight:
dist[neighbor] = dist[u] + weight
heapq.heappush(q, [dist[neighbor], neighbor])
return dist
# Example usage:
V = 5
src = 0
adj = [
[(1, 4), (2, 8)],
[(0, 4), (4, 6)],
[(0, 8), (3, 2)],
[(2, 2), (4, 10)],
[(1, 6), (3, 10)]
]
print(dij(V, adj, src))
