Standard Bar Graphs · Shortest Path Problems O((V + E) log V) · O(V + E)
A freight network links depots with toll roads of varying cost, and dispatch must quote every depot its cheapest total toll from the home hub. The dispatcher always settles the cheapest unsettled depot next — once settled, its quote is final — and tries to improve each neighbour's quote through it. A priority queue keeps the cheapest unsettled depot on top.
Input: An integer n (vertices 0..n-1), an adjacency list adj where adj[i] holds pairs [neighbour, weight] for each undirected edge, and the source vertex s.
Output: Return the array of shortest distances from s to every vertex.
1 <= n <= 10^51 <= weight <= 10^6The graph is undirected and connectedInput: {"n":5,"s":0,"adj":[[[1,2],[2,4]],[[0,2],[2,1],[3,7]],[[0,4],[1,1],[4,3]],[[1,7],[4,2]],[[2,3],[3,2]]]}
Output: [0,2,3,8,6]
The hub settles 1 (toll 2) before 2 (direct 4); 2 improves to 3 via 1, and the rest follow.
Input: {"n":3,"s":0,"adj":[[[1,5],[2,1]],[[0,5],[2,2]],[[0,1],[1,2]]]}
Output: [0,3,1]
Vertex 1 is cheaper through the low-toll bridge: 1 + 2 = 3 beats the direct 5.