Back to problems
COMP2521
Dijkstra: Shortest Distances from 0
Dijkstra: Shortest Distances from 0
Given a non-negative weighted undirected graph, find the shortest distance from node 0 to every node; print -1 for unreachable.
Input: line 1 V E; then E lines u v w (undirected edge of weight w).
Output: one line of V integers, the i-th is dist(0, i) or -1, space-separated.
Use a min-heap: pop the nearest unvisited node, relax its neighbours.
Samples
stdin
5 7 0 3 1 0 1 6 3 1 2 3 4 1 1 4 5 1 2 5 4 2 5
expected
0 3 7 1 2
python3
14