Clinic #25: Network Delay Time

Pattern: Graphs / Dijkstra · LC 743

Five towns joined by one-way roads, a travel time on every road, and the earliest arrival written beside each town. This clinic uses that same five-point map, drawn as a table of falling dominoes.

Before you start. You need a list, and the habit of keeping a running smallest number while you read it. Dots joined by lines (a graph) are introduced in Graphs (BFS, DFS, Dijkstra, topological sort), and Shortest Paths, Worked (Dijkstra, Bellman-Ford, A*) traces this same map three ways; neither is needed first, because everything below is built by hand from one small table.