Shortest path algorithms

Applications

Three flavors: Source-Target, Single Source, All Pairs

Source-Target (s-t)

Problem definition: Given a weighted graph, find the shortest path from $s$ to $t$ (so the cost of path, the sum of edge costs in path, is minimized). If the graph is directed, directions of the edges need to be respected.

Weights are arbitrary numbers: not necessarily distances; need not satisfy the triangle inequality
Worst case performance: the same as the algorithm for finding the shortest directed paths from a source vertex to every other vertex.
If the graph is not connected, there are some vertices v,v' not connected by any path; in that case, d(v,v') = +∞.
A* algorithm to source-target: starting from a source node, A* algorithm constructs a tree of paths starting from that node, expanding paths one step at a time, until one of its paths ends at the target (goal) node. Applications: robot's path planning; game AI. Read more.

Single Source

Problem definition: Given weighted graph and single source s, find distance (and shortest path) from s to every other vertex.
Shortest paths form a tree.

Algorithms for single source shortest path problem: BFS, Dijkstra's, Bellman-Ford

BFS (for unweighted graphs)
However, when weights are added, BFS will not give the correct answer.
Review of BFS:

BFS(s): 
   toVisit = {s} //toVisit is a queue
   while toVisit is not empty:
       u = toVisit.dequeue()
       for u's every unvisited neighbor v:
	  toVisit.enqueue(v)
          dist[v] = ?? //complete it to solve the shortest path problem

Dijkstra's algorithm (fastest algorithm for graphs that don't contain negative weights)
The algorithm was invented by dutch computer scientist Edsger Dijkstra in 1959. Dijkstra's algorithm can be described as a generalized form of BFS, in which the order of traversed nodes is not determined by number of edges from the source node, but by the distance from the source (sum of weights of all edges along the path from source to the given node). Whenever a vertex $v$ is processed, the $dist[x]$ is updated for every neighbor $x$ of $v$. Finding u-v that minimizes dist[u] + e.weight() in V steps (smallest dist[] value among vertices in S') can be done by scanning through the list of unvisited vertices, which results in a time complexity of $\Theta(|V|^2)$. However, more efficient implementations of the Dijkstra's algorithm are available (e.g., using a priority queue).
The algorithm:
```
   S: set of vertices for which the shortest path length from s (the source vertex) is known.
   Initialize:
       S to {},
       set dist[s] to 0 for the source node,
       set dist[v] to infinity for all other nodes v
   Repeat until S contains all vertices connected to s:
      * find vertex v that is closest to s (with minimum dist)
        (implementation detail for this step determines the asymptotic complexity of the algorithm)
      * update dist[x] for every neighbor x of v: dist[x]=min{dist[v]+weight(v->x),dist[x]}
      * add v to S
```
Note that Dijkstra's algorithm requires that weights of all edges are non-negative. Otherwise the procedure is not able to determine whether the shortest path for the node was already found or not. Is Dijkstra's a DP or a greedy algorithm? ("Djikstra as a DP method which relies on greediness to pick the order in which the sub-problems are solved. It's not a counter from i=0 through n, instead, it is computed after every vertex is taken care of")
The textbook example:

More examples: undirected graph; directed graph
ShortestPath.java

The Bellman-Ford algorithm (based on the relaxation operation, for any graph)
Edge relaxation

For any node v,
      dist[v] is the length of some path from the source s to the node v
      previous[v] is the vertex before v (in the path from s to v)

Relaxation along edge from u to v (e):  
  * dist[u] starts as the length of some path from s to u
  * dist[v] starts as the length of some path from s to v
  * if u-v gives a shorter path to v through u, update dist[v] and previous[v].

Relax(u, v, e):
   if(dist[v] > dist[u] + e.weight()):
         dist[v] = dist[u] + e.weight()
         previous[v] = u;

Properties of edge relaxation:

the edge relaxation operation is safe, i.e.
- the starting value of dist[v]
- is >= than any dist[v] value
- obtained by relaxation (for all v in V)
how do we prove that relaxation will not cause the value of dist[v] to become larger?

Relaxation sets dist[v] to the length of a shorter path from s to v
    if u-v provides such a path

The Bellman-Ford algorithm pseudocode

 
   for v in 1 to |V|:
       dist[v] = INF 
       previous[v] = null
   dist[s] = 0 #s is the source
   repeat |V|-1 times: #why?
       for every edge e (from u to v) in E:
           if dist[u] + e.weight() < dist[v]:
               dist[v] = dist[u] + e.weight()
               previous[v] = u

The algorithm calculates shortest paths in a bottom-up manner: it first calculates the shortest distances which have at most one edge in the path; it then calculates shortest paths with at most 2 edges, and so on. There can be maximum |V| – 1 edges in any simple path, so the outer loop runs |v| – 1 times. The asymptotic complexity of Bellman-Ford algorithm is $O(|V||E|)$.

All-Pairs Shortest Path

Apply a single source algorithm (BFS for unweighted, Dijkstra's or Bellman-Ford's algorithm) to every vertex
Floyd's algorithm

Floyd's algorithm is a dynamic programming (DP) algorithm.
Intuitively, we would like to reuse results from previous shortest path computations (subproblems) to compute other shortest paths in the graph.
How Floyd's algorithm works?
Define a $k$-path from vertex u to vertex v to be
    any path whose intermediate vertices (aside from u and v)
    all have indices less than k.
A 0-path is defined to be direct edge from u to v.

For example: Path 3, 0, 2 (the numbers are the indices of the vertices)
    is a 1-path,
    as well as a 2-path, a 3-path, and a 4-path,
    but NOT a 0-path.

Define $d_k(u, v)$ to be the length
    of the shortest $k$-path from vertex u to vertex v.

The shortest $(k+1)$-path either goes through vertex $k$ or it does not:
$d_{k+1}(u, v) = min[d_{k}(u, v), d_{k}(u,k) + d_{k}(k, v)]$ (the recursive definition)

See a pseudocode

find-all-shortest-paths():
    //Initialization: only consider 0-paths 
    for every i and j: 
	d(i, j) = 0 if i == j
                = weight of the edge, if there is one from i to j
                = infinity, otherwise
    //update the d(i, j) 
    for (k = 0; k < |V|; k ++) //(k+1)-path
	for (i = 0; i < |V|; i ++) 
            for (j = 0; j < |V|; j ++) 
                if d(i,j) > d(i,k) + d(k,j) 
                    d(i,j) = d(i,k) + d(k,j)

The DP algorithm runs in O(|V|³) time.
See an example: