Network Delay Time
A network of n nodes has directed edges with positive travel times. A signal is sent from node k. Return how long it takes for every node to receive it, or -1 if some node is unreachable.
- 1 ≤ n ≤ 100
- 1 ≤ times.length ≤ 6000
- 1 ≤ w ≤ 100
- Weighted edges with non-negative weights
- Single source, need distances to all nodes
- Answer = maximum of the shortest distances
Once edges have different costs, BFS order is wrong and you need to expand nodes by accumulated distance: Dijkstra with a min-heap for non-negative weights. Negative weights or a "at most k edges" bound push you to Bellman-Ford (k rounds of relaxation); "every pair" on a small dense graph is Floyd-Warshall.
Run Dijkstra from k with a min-heap keyed by tentative distance. Pop the closest unfinalised node, skip stale entries, and relax each outgoing edge, pushing improved distances. Once the heap empties, the answer is the largest finite distance; if any node remains at infinity return -1. Non-negative weights guarantee that a popped node's distance is final.
- Bellman-Ford runs in O(V · E) and is simpler for tiny graphs; Floyd-Warshall in O(V^3) is fine at n = 100 but computes far more than needed.