Shortest-Path System Design — Choice by Edge Weight

City = graph vertices = locations, edges = roads, weight = length/time.

(i) All roads equal length (unweighted)

Algorithm: Breadth-First Search (BFS)

• Reason: BFS explores in increasing distance (number of edges) layers → first time target dequeued, its distance is minimum edges. $O(V+E)$ with adjacency list, no need for priority queue.
• Alternative: Dijkstra with uniform weight 1 reduces to BFS (overhead wasteful).
• Use queue: dist[s]=0, push neighbors.

(ii) Varying lengths, no negative weights (positive weighted)

Algorithm: Dijkstra's Algorithm (with binary heap $O((V+E)\log V)$, Fibonacci $O(E+V\log V)$)

• Reason: Greedy choice of smallest tentative distance; proof relies on non-negative weights (once vertex extracted, distance final). Handles varying positive weights optimal.
• Steps: dist[s]=0, priority queue keyed by dist; repeatedly extract min $u$, relax edges $u→v$: if $dist[u]+w(u,v)<dist[v]$ update.
• Why not Bellman-Ford? Correct but $O(VE)$ slower, unnecessary without negatives.
• Why not BFS? BFS assumes uniform weight → would give wrong result.

(iii) Some roads have negative lengths (negative weights, but no negative cycles reachable)

Algorithm: Bellman-Ford Algorithm ($O(VE)$) — or SPFA / Johnson's if many sources.

• Reason: Dijkstra fails with negative edges (greedy finality broken; example $s→a$ weight5, $s→b$ weight6, $b→a$ weight -4 → shortest to $a$ is via $b$ (2) not direct 5, Dijkstra would finalize $a$ too early).
• Bellman-Ford relaxes all edges $V-1$ times, then one more pass detects negative cycles.
• If negative cycle exists, shortest path undefined ($-\infty$); Bellman-Ford reports it.
• If graph large and only few negatives, could use Johnson's ($O(VE\log V)$) reweighting.

Summary Table

Case	Weights	Algorithm	Time	Handles negatives?
(i)	uniform	BFS	$O(V+E)$	No need
(ii)	$≥0$ varying	Dijkstra (heap)	$O(E\log V)$	No
(iii)	arbitrary (no neg cycle)	Bellman-Ford	$O(VE)$	Yes + detects cycle

Justification: Choose simplest correct algorithm for constraint; progressing BFS → Dijkstra → Bellman-Ford as generality increases, trading speed for correctness.