Network Delay Time - Video Solutions

Problem Overview: A signal starts from node k and travels through a directed weighted graph. Each edge (u, v, w) represents a travel time w. The goal is to determine how long it takes for the signal to reach every node. If any node is unreachable, return -1. Otherwise return the maximum shortest-path distance from k to all nodes.

Approach 1: Dijkstra's Algorithm (Time: O(E log V), Space: O(V + E))

This problem is a classic shortest path scenario on a weighted directed graph with non‑negative edge weights. Build an adjacency list from the input edges, then run Dijkstra starting from node k. Maintain a distance array where dist[i] stores the shortest time to reach node i. Use a priority queue (min‑heap) to always process the node with the smallest known distance. For each popped node, iterate through its neighbors and relax edges by updating distances if current + weight is smaller. After processing all reachable nodes, the answer is the maximum value in the distance array. If any node still has infinite distance, the graph is disconnected and the result is -1.

Dijkstra works well because edge weights are non‑negative and we only need the shortest path from one source. The heap ensures we always expand the next closest node, keeping the algorithm efficient even for large graphs.

Approach 2: Bellman-Ford Algorithm (Time: O(V * E), Space: O(V))

The Bellman‑Ford algorithm computes shortest paths by repeatedly relaxing all edges. Initialize distances with infinity except the source node k. Then iterate n-1 times over the edge list. For each edge (u, v, w), update dist[v] = min(dist[v], dist[u] + w). Each iteration propagates shorter paths across the graph until the optimal distances stabilize.

This approach does not require a heap or adjacency list and works even when negative weights exist (though this problem doesn't include them). Its simplicity makes it easy to implement, but the O(V * E) complexity is significantly slower than Dijkstra for dense graphs. It still reliably solves the problem and is useful for understanding fundamental graph relaxation techniques.

Recommended for interviews: Dijkstra’s algorithm is the expected solution. Interviewers want to see that you recognize the problem as a single‑source shortest path on a weighted graph and immediately reach for a min‑heap based approach. Bellman‑Ford demonstrates understanding of edge relaxation and graph fundamentals, but Dijkstra shows stronger algorithmic optimization and is the standard answer.