Shortest Paths

A shortest path minimizes the sum of edge weights. The correct algorithm depends primarily on the weight model.

Selection guide

Weights / query	Algorithm
Unweighted	BFS
Only 0 or 1	0–1 BFS with a deque
Non-negative	Dijkstra
Negative edges allowed	Bellman–Ford
All vertex pairs, moderate dense graph	Floyd–Warshall
Goal-directed with admissible heuristic	A*

Dijkstra's algorithm

Maintain tentative distances and repeatedly finalize the unsettled vertex with minimum distance using a priority queue. Relaxing u → v tests whether distance[u] + weight(u,v) improves distance[v].

The greedy step is safe because every not-yet-explored continuation has non-negative cost. A negative edge can reveal a cheaper route after a vertex was considered final, invalidating the proof.

With adjacency lists and a binary heap, a common implementation takes O((V + E) log V) time and O(V + E) graph-plus-working storage. Java priority queues commonly handle a decreased distance by inserting a new entry and discarding stale entries when removed.

Bellman–Ford

Relax every edge V - 1 times. Any simple shortest path has at most V - 1 edges. A further successful relaxation identifies a negative-weight cycle reachable from the source, so finite shortest distances are undefined for vertices reachable through that cycle. Time is O(VE).

Floyd–Warshall and A*

Floyd–Warshall uses dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for successive permitted intermediate vertices, taking Θ(V³) time and Θ(V²) space. A* prioritizes estimated total cost; an admissible heuristic preserves optimality, while consistency simplifies graph-search behavior.

Exercises

1. Give a graph where Dijkstra fails with a negative edge.
2. Add predecessor tracking and reconstruct a path.
3. Explain how integer overflow can corrupt relaxation.