Shortest Path Problem

Useful Resources

Problem definition

Given a directed or undirected graph $G(V,E)$, find the shortest path from one vertex $u$ to another vertex $v$.

The above problem the basic problem, which is single-source single-destination problem. There are also variations:

  • The single-source shortest path problem, in which we have to find shortest paths from a source vertex $v$ to all other vertices in the graph.
  • The single-destination shortest path problem, in which we have to find shortest paths from all vertices in the directed graph to a single destination vertex $v$. This can be reduced to the single-source shortest path problem by reversing the arcs in the directed graph.
  • The all-pairs shortest path problem, in which we have to find shortest paths between every pair of vertices $u, v$ in the graph.

Common Algorithms

Below are the most important algorithms for solving the shortest path problem.

Dijkstra’s algorithm

The Dijkstra’s algorithm can solve both single-source single-target problem and single source problem. There are two features of the algorithm:

  • It is a greedy algorithm.
  • It use breath first search (BFS) to find the shortest path.

Time complexity: $O(V^2)$.

The pseudo code is as follows.

function Dijkstra(Graph, source):
	create vertex set Q
    
    for each vertex v in Graph:             
    	dist[v] ← INFINITY                  
		prev[v] ← UNDEFINED                 
		add v to Q                      
	dist[source] ← 0                        
 
	while Q is not empty:
		u ← vertex in Q with min dist[u]    
                                            
        remove u from Q 
        
        for each neighbor v of u:           // only v that are still in Q
	        alt ← dist[u] + length(u, v)
            if alt < dist[v]:               
                dist[v] ← alt 
                prev[v] ← u 
                
    return dist[], prev[]

The code solves the single-source problem, i.e. it finds shortest paths for all other nodes. If we are only interested in finding the shortest path from source to destination, we don’t need to traverse all $Q$. When prev[u] == target, we can terminate the algorithm.

Bellman-Ford algorithm

The Bellman-Ford algorithm can solve single-source problem in a weighted digraph. Although it is slower than the Dijkstra’s algorithm for the same problem, it is more versatile because it can handle the graphs with negative edge weight.

If a graph contains a “negative cycle” that is reachable from the source, then there is no cheapest path: any path that has a point on the negative cycle can be made cheaper by one more walk around the negative cycle. The Bellman-Fold algorithm can detect and report the negative cycle.

The Bellman-Ford algorithm is very like the value iteration in optimal control. In optimal control, we first partition the state space and input space, and then assign $\infty$ to each state as the initial value. Next, we perform Bellman’s equation: $V_{k+1}(x) \gets \min_u g(x, u) + V_k(f(x,u))$ to update the value at state $x$ until $V_{k+1}$ and $V_k$ are close enough.

In the Bellman-Fold algorithm, the vertices are like states $x$ and link weights are like inputs $u$. But unlike the valuation iteration in the optimal control, we are sure that the value (which is the distance) must converge in $\vert V \vert-1$ steps as there is only $\vert V \vert - 1$ states in total. Another understanding is the following. At each iteration $i$ that the edges are scanned, the algorithm finds all shortest paths of at most length $i$ edges (and possibly some paths longer than $i$ edges). Since the longest possible path without a cycle can be edges $\vert V \vert - 1$ edges, the edges must be scanned $\vert V \vert - 1$ times to ensure the shortest path has been found for all nodes.

Time complexity: $O(VE)$.

The pseudo code is as follows.

function BellmanFold(Graph, source):
	create vertices list V and edges list E
	
	// Step 1: initialize graph
	for each vertex v in V do
		dist[v] := inf
		pred[v] := Null
	
	dist[source] := 0 	// the distance from the source is zero
	
	// Step 2: do distance iteration
    for i from 1 to |V|-1 do 	// i is never referenced, only a counter
    	for each edge (u,v) with weight w in E do 
    		if dist[u] + w < dist[v] then
    			dist[v] := dist[u] + w
    			pred[v] := u
    
    // Step 3: check for negative-weight cycles
    for each edge (u,v) with weight w in E do
    	if dist[u] + w < dist[v] then
    		error "Graph contains a negative-weight cycle."
    
    return dist[], pred[]

Note that since the Step 2 has already find the best distance dist function, which is equivalent to the value function. Therefore, if all weights are nonnegative, then for every edge $(u,v)$, we should have dist[u] + w = dist[v]. If it is not satisfied, there must be a negative-weight cycle.

Floyd–Warshall algorithm

This algorithm can be used for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). It solves the all-pair problem.

The main idea of the algorithm uses dynamic programming. Given a graph $G(V,E)$, we number the vertices as $1,2,\dots, N$ where $N = \vert V \vert$. Consider a function $f(i,j,k)$ which represents the shortest path from node $i$ to node $j$ passing through nodes ${ 1,2,\dots, k }$. Note that a path from $i$ to $j$ using the intermediate nodes ${1,2,\dots, k}$ has two possibilities.

  • The path only use the intermediate nodes ${1,2,\dots, k-1}$.
  • The path first pass from node $i$ to node $k$ using ${1,2,\dots, k-1}$, and then pass from node $k$ to node $j$ using ${1,2,\dots, k-1}$.

Therefore, this gives a recursive formula

\[f(i,j,k) = \min\{ f(i,j,k-1), f(i,k,k-1) + f(k,j,k-1) \}, f(i,j,0) = w(i,j).\]

We want to find $f(i,j,N)$.

Time complexity: $O(V^3)$.

The pseudo code is as follows.

function FloydWarshall(Graph):
	let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
	for each edge (u, v) do
    	dist[u][v] ← w(u, v)  // The weight of the edge (u, v)
	for each vertex v do
    	dist[v][v] ← 0
	for k from 1 to |V|
    	for i from 1 to |V|
        	for j from 1 to |V|
            	if dist[i][j] > dist[i][k] + dist[k][j] 
                	dist[i][j] ← dist[i][k] + dist[k][j]
            	end if