Shortest Path Algorithms

Dijkstra's algorithm finds the shortest path from a single source vertex $s$ to every other vertex in the graph, but it requires all edge weights to be non-negative. The core strategy is greedy: at every step, we pick the unvisited vertex with the smallest known distance, mark it as finalized, and relax all of its outgoing edges.

Think of it like water spreading outward from a source, but unlike BFS (which spreads in equal steps), Dijkstra always expands to the "nearest" unexplored point first, where "nearest" accounts for edge weights.

At each step, Dijkstra picks the unvisited vertex $u$ with minimum tentative distance $dist[u]$, and declares this distance final. This is correct only because all weights are non-negative. If $u$ has the smallest tentative distance among all unvisited vertices, then any other path to $u$ through a vertex that is not yet finalized would have to pass through an edge with non-negative weight, making that alternate path's length at least as long as $dist[u]$ already is. So no shorter path to $u$ can possibly be discovered later.

The running time depends entirely on how the priority queue is implemented:

• Simple array: Finding the minimum each time takes $O(V)$ (linear scan), done $V$ times, giving $O(V^2)$ for Extract-Min calls. Each edge relaxation is $O(1)$, giving $O(E)$ total for relaxations. Total: $O(V^2 + E) = O(V^2)$ (since $E \le V^2$).

• Binary min-heap: Extract-Min takes $O(\log V)$, done $V$ times: $O(V \log V)$. Decrease-Key takes $O(\log V)$, done at most $O(E)$ times: $O(E \log V)$. Total: $O((V+E) \log V)$.

• Fibonacci heap (advanced): Extract-Min is $O(\log V)$ amortized, Decrease-Key is $O(1)$ amortized, giving $O(E + V \log V)$, the best known bound.

For dense graphs ($E \approx V^2$), the simple array is actually competitive or better. For sparse graphs ($E \approx V$), the heap-based version is much faster.

Dijkstra's greedy strategy relies on the assumption that once a vertex is finalized (marked visited with its minimum distance locked in), no future relaxation can ever improve it. This assumption breaks if negative edge weights exist, because a path through a vertex we haven't visited yet (which currently looks "farther") could later take a very negative edge and become shorter overall than what we already finalized.

Bellman-Ford also finds shortest paths from a single source, but unlike Dijkstra, it works even when edge weights are negative (as long as there is no negative weight cycle reachable from the source). Instead of greedily picking the closest vertex, Bellman-Ford takes a simpler, more brute-force approach: relax every single edge, and repeat this entire process $V-1$ times.

A shortest path between any two vertices in a graph with $V$ vertices can have at most $V-1$ edges (since a simple path visits at most $V$ vertices, hence at most $V-1$ edges; a path with a cycle is never shorter than the same path with the cycle removed, as long as there's no negative cycle).

Each full pass over all edges guarantees that the shortest path using at most $k$ edges is correctly computed after the $k$-th pass. So after $V-1$ passes, we are guaranteed to have found the shortest path using at most $V-1$ edges, which covers every possible simple shortest path in the graph.

After the $V-1$ main iterations, we do one more pass over all edges. If any edge can still be relaxed (i.e., $dist[u] + w(u,v) < dist[v]$), this means the shortest path estimate is still improving beyond what $V-1$ edges should allow. This can only happen if there is a negative weight cycle reachable from the source, since such a cycle allows us to keep looping around it, making the "shortest path" infinitely small (undefined).

Floyd-Warshall solves the all-pairs shortest path problem: finding the shortest distance between every pair of vertices $(i,j)$, all at once. It uses dynamic programming, based on a simple but powerful idea: for every pair $(i,j)$, we consider whether the shortest path should pass through an intermediate vertex $k$, trying every possible $k$, one at a time.

Let $d^{(k)}[i][j]$ denote the shortest path from $i$ to $j$ using only vertices $\{1, 2, \ldots, k\}$ as intermediate vertices (the endpoints $i$ and $j$ themselves are always allowed). The recurrence is: \[ d^{(k)}[i][j] = \min\Big(d^{(k-1)}[i][j], \; d^{(k-1)}[i][k] + d^{(k-1)}[k][j]\Big) \] In words: the shortest path either does not use vertex $k$ at all (so it's the same as before), or it does pass through $k$ (so it splits into a path from $i$ to $k$, plus a path from $k$ to $j$, both using only vertices up to $k-1$). We take the smaller of these two options. The base case is $d^{(0)}[i][j] = w(i,j)$ (direct edge weight, or $\infty$ if no edge, and 0 if $i=j$).

Since each $d^{(k)}$ only depends on $d^{(k-1)}$, we can use a single 2D array and update it in-place as $k$ increases from 1 to $V$.

Three nested loops, each running $V$ times, gives $\Theta(V^3)$ time. We store a $V \times V$ matrix, giving $\Theta(V^2)$ space. This is efficient for dense graphs where we want all-pairs distances; running Dijkstra from every vertex would take $O(V \cdot (V+E)\log V)$, which for dense graphs ($E \approx V^2$) becomes $O(V^3 \log V)$, actually worse than Floyd-Warshall's clean $O(V^3)$.

1. Are all weights 1 (unweighted)? Use BFS. Simplest and fastest, $O(V+E)$.

2. Single source needed, and are all weights non-negative? Use Dijkstra. It is the fastest correct algorithm for this case.

3. Single source needed, but negative weights possible? Use Bellman-Ford. Slower, but correctly handles negatives and can detect negative cycles.

4. Need distances between every pair of vertices? Use Floyd-Warshall if the graph is dense or $V$ is small-to-moderate. If the graph is sparse and weights are non-negative, running Dijkstra from each vertex can be faster.