Problem. A network has n nodes and directed edges (u, v, w): a signal from u reaches v after w time units (w ≥ 0). A
signal is sent from node k. Return the time until all nodes have received it, or −1 if some node never does.
times = [(2, 1, 1), (2, 3, 1), (3, 4, 1)], n = 4, k = 2 → 2
times = [(1, 2, 1)], n = 2, k = 2 → −1 (node 1 is unreachable)
Each node receives the signal at its shortest-path distance from k; the answer is the largest of these. With weights, BFS levels no longer equal distances (a path of three cheap edges can beat one expensive edge), so we need a weighted shortest-path algorithm.
ML context. Model serving is a graph of services (gateway, retriever, reranker, model shards) with latencies on each hop; the time until a request can reach every shard, or the fastest route to one service, is a shortest-path question. Routing inference requests across regions, choosing the cheapest chain of conversions between data formats, and planning in RL environments with costs all run Dijkstra or a variant.