Shortest paths with weights

Before you start

• Heap

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

  Open lesson

Why it matters

Routing systems and latency monitors need earliest arrival times across links with different costs. Treating every link alike gives wrong routes, while rescanning every edge for every node wastes work on nonnegative networks. The shortest arrival to every reachable node must be found without V full edge scans, and negative weights are not allowed.

times[i] = [u, v, w] is a directed edge of weight w. Send a signal from node k. Return the time until every node receives it, or -1 if some node is unreachable. Nodes are labeled 1..n.

Input

times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1], [3, 4, 5]], n = 4, k = 1

Output

4

For times [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1], [3, 4, 5]], Bellman-Ford rescans all five edges three times. A heap settles 1 at 0, 3 at 1, 2 at 3, and 4 at 4.

Starting at k = 1, pop (0, 1) and offer node 2 at distance 4 and node 3 at 1. Pop (1, 3) next; it improves node 2 to 3 and offers node 4 at 6. Because all weights are nonnegative, no later candidate can improve settled node 3.

Pop (3, 2) and offer node 4 at 4, then settle node 4 at 4. Entries (4, 2) and (6, 4) are stale because those nodes already have smaller settled distances, so skip them. The largest final distance is 4.