Shortest Path Algorithms

Opening scenario

Network Delay Time (LC 743): n nodes; times[i] = [u, v, w] is a directed edge with travel time w. A signal starts at node k. Return the time for all nodes to receive it, or -1 if some node can't. Follow-up you should expect: Cheapest Flights Within K Stops (LC 787) — given flights [from, to, price], return the cheapest price from src to dst using at most k stops, or -1 if there is no such route.

LC numbers identify LeetCode problems.

For LC 743, nodes are labeled 1 through n, k is a valid source, and weights are nonnegative. LC 787 labels cities 0 through n-1 and uses nonnegative prices. A stop is an intermediate city: src → a → dst has one stop and two edges. Below, V is the number of vertices and E the number of edges. Compare routes by total weight, then ask whether the edge-count limit changes what you must remember about an arrival.