Weighted graphs: shortest paths and spanning trees interview questions

Start from n separate points: each link merges at most two groups into one, so connecting everything takes at least n − 1 links. A cheapest network never needs more. If it contained a cycle, removing any one link of that cycle would keep every point connected, because the rest of the cycle still joins the two ends of the removed link, and the network would cost no more. Removing links from cycles until none is left gives a connected network without cycles, which is a tree, and every tree on n points has exactly n − 1 links. With every length above zero, a cheapest network is therefore always a tree; with links of length 0 a network with a cycle can tie, but a tree of the same cost always exists.

If the road from a to b lies on a cycle, the rest of the cycle is a second route from a to b. Closing the road then splits nothing: any trip that used it can take that route instead, so every pair of towns that could meet still can. If the road lies on no cycle, there is no other route from a to b, because such a route plus the road would be a cycle. Closing it therefore leaves a and b unable to reach each other, which splits their group. A doubled road, a road and its bypass between the same two towns, is a cycle of two roads, so neither copy is critical. In a tree every road is critical, and in a ring none is.

Suppose the condensation had a cycle through components X and Y. Then some node of X reaches some node of Y, and some node of Y reaches back into X. Inside a component every node reaches every other, so every node of X would reach every node of Y and the other way round. Then X and Y together would be a group of mutual reachability larger than X, which contradicts X being a largest such group. So the condensation is a directed acyclic graph: it has a topological order, at least one source with no edge coming in and at least one sink with no edge going out, and dynamic programming over it works the way it does on any DAG.

Because that keeps the deque sorted by distance. When an entry of distance d leaves the front, everything still waiting has distance d or d + 1. A zero-cost move gives its neighbour distance d, the smallest possible, so it belongs in front of everything; a costly move gives d + 1, the largest possible, so it belongs behind everything. With those two rules the distances never decrease from front to back and never differ by more than 1, so entries leave the deque in the same order as they would leave a min-heap, and the argument that makes Dijkstra's algorithm correct applies. Each push and pop costs O(1) instead of O(log n), so the whole search runs in O(V + E). Pushing every move to the back, as plain BFS does, lets an entry of d + 1 come out before one of d.

With moves up, down, left and right, each step changes the row or the column by exactly 1, so any route from a cell to the goal needs at least as many steps as the Manhattan distance, |dr| + |dc|. Every step costs at least 1, so the route costs at least that much: the estimate never exceeds the true remaining cost, which is what admissible means. It stops being admissible as soon as a step can cover more than one unit of Manhattan distance for less than its length: diagonal moves, where one step covers 2 units, teleport pads, or steps that cost less than 1, such as a conveyor belt. Then the estimate must be rebuilt from the moves that exist, so that it still never exceeds the cheapest way to cover the remaining distance.