Dijkstra's Shortest Path
- 2 min read
- Graph
- Algorithm
- Shortest Path
3 years ago
Assuming input is as follows:
7 6 # num nodes, num edges
1 # source node
1 2 1 # path from 1 to 2 with weight 1
2 3 2 # and so on...
2 4 1
3 5 4
4 5 5
5 6 1
import heapq
n, m = map(int, input().split())
s = int(input())
graph = [[] for _ in range(n)]
for _ in range(m):
u, v, w = map(int, input().split())
graph[u - 1].append((v - 1, w))
graph[v - 1].append((u - 1, w))
dist = [float('inf')] * n
dist[s - 1] = 0
pq = [(0, s - 1)]
while pq:
d, node = heapq.heappop(pq)
for neighbor, weight in graph[node]:
new_dist = dist[node] + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
print(*[-1 if d == float('inf') else d for d in dist])
Why is a visited set not needed?
Just to explain a bit more, think about the role of the priority queue. It contains the nodes, ordered by the shortest known path to them. When extracting a node from the queue, all nodes before where at most as far away as that node and all nodes after will be at least as far away as that node. Since all nodes that were closer were already processed, any new path discovered to one of these nodes there will be via a node that is at least as far away. This means that there can't be any shorter route to an extracted node coming from a node that is still in the queue, so the mere check new_dist < dist[neighbour] will already exclude those nodes that were scanned. Source