dij
12345678910111213141516171819202122232425262728293031
import heapq
def dij(graph,start):
dist = {
0: float('inf'),
1: float('inf'),
2: float('inf'),
3: float('inf')
}
dist[start]=0
heap=[]
heapq.heappush(heap,(0,start))
while heap:
curr,node=heapq.heappop(heap)
for neighbour,weight in graph[node]:
new_dist=curr+weight
if new_dist<dist[neighbour]:
dist[neighbour]=new_dist
heapq.heappush(heap,(new_dist,neighbour))
return dist
graph = {
0: [(1, 1), (2, 4)], # Node 0 → Node 1 (weight 1), Node 2 (weight 4)
1: [(0, 1), (2, 2), (3, 5)], # Node 1 → Node 0, Node 2, Node 3
2: [(0, 4), (1, 2), (3, 1)],
3: [(1, 5), (2, 1)]
}
for i in range(4):
shortest_distances = dij(graph, i)
print(shortest_distances)
Python
INFO