Weighted Shortest Paths (Dijkstra)

Foundations

In the first lesson, every arrow only meant before or after. Now, what if each edge has a cost, such as a travel time, and you need the cheapest total cost from one start to every node?

Store weighted edges in the adjacency list as pairs, (neighbor, weight). Dijkstra's algorithm keeps a frontier of tentative distances in a min-heap: pop the closest node not yet settled, settle it, and relax its edges by pushing d + w for each neighbor. With no negative weights, nothing popped later can be closer, so a node's first pop is final, and later entries for it are stale.

Take adj = [[(1, 4), (2, 1)], [(3, 1)], [(1, 2), (3, 5)], [(4, 3)], []] from node 0. Settle 0 at 0 and push 1 at 4 and 2 at 1. Settle 2 at 1, which offers 1 at 3 and 3 at 6. Settle 1 at 3, beating the direct 4, then 3 at 4 and 4 at 7. The distances are [0, 3, 1, 4, 7].

• Heap

  Dijkstra's algorithm is a loop around a min-heap. That lesson covers heapq.

  Open lesson

Case Scenario

Network Delay Time sends a signal from node k along directed edges times[i] = [u, v, w], where w is the travel time, and asks when the last node hears it, or -1 if some node never does. That is Dijkstra from k, and the answer is the largest settled distance. In the example, node 2 hears it at 3 by way of node 3, and node 4 is last, at 4.

The direct approach, Bellman-Ford, relaxes every edge, lowering a node's distance whenever dist[u] + w beats it, and repeats that V - 1 times: O(V · E). It even handles negative weights, but on a graph without them it keeps rescanning edges whose endpoints are already final.