Step 5 of 6
Dijkstra's shortest paths
When edges have different weights (distances, latencies, costs), BFS is no longer enough. Dijkstra's algorithm is BFS with a priority queue: always expand the unfinished vertex with the smallest known distance.
dist[src] = 0; heap = {(0, src)}
while heap not empty:
(d, v) = pop smallest
if d > dist[v]: continue // stale entry, skip it
for each edge (v, w, cost):
if dist[v] + cost < dist[w]:
dist[w] = dist[v] + cost; push (dist[w], w)
O((V + E) log V). It requires non-negative weights. It's the algorithm behind route planners and network routing protocols like OSPF.
Your turn: write std::vector<long long> dijkstra(int n, const std::vector<Edge>& edges, int src) for a directed graph. Unreachable vertices get -1.