[Algorithm 101] Shortest Path Problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

Dijkstra’s algorithm

For a given vertex called the source in a weighted connected graph, Dijkstra’s Algorithm can find the shortest paths to all the graph’s other vertices. This algorithm is applicable to both undirected and directed graph, but it’s subject to graph with non-negative weights only.

First, it finds the shortest path from the source to a vertex nearest to it, then to a second nearest, and so on.  In general, before its ith iteration commences, the algorithm has already identified the shortest paths to i - 1 other vertices nearest to the source.  These vertices, the source, and the edges of the shortest paths leading to them from the source form a tree T_{i} of the given graph:

Since all the edge weights are non-negative, the next vertex nearest to the source can be found among the vertices adjacent to the vertices of T_{i}. The set of vertices adjacent to the vertices in T_{i} can be referred to as “fringe vertices”; they are the candidates from which Dijkstra’s algorithm selects the next vertex nearest to the source. (Actually, all the other vertices can be treated as fringe vertices connected to tree vertices by edges of infinitely large weights). To identify the ith nearest vertex, the algorithm computes, for every fringe vertex u, the sum of the distance to the nearest tree vertex v (given by the weight of the edge (v, u)) and the length d_{v} of the shortest path from the source to v (previously determined by the algorithm) and then selects the vertex with the smallest such sum. The fact that it suffices to compare the lengths of such special paths is the central insight of Dijkstra’s algorithm.

Dijkstra's algorithm

 

Bellman-Ford algorithm

Bellman-Ford algorithm is similar to Dijkstra’s algorithm but it can work with graphs in which edges could have negative weights. Furthermore, if there exists a negative weight cycle(i.e. a cycle whose edges sum to a negative value), then there will be no shortest path, and this can be also detected by Bellman-Ford algorithm. This algorithm is based on the following crucial observation:

If graph G has no negative cycles, then there is a shortest path from s to t that is simple (i.e., does not repeat nodes), and hence has at most n-1 edges.

This algorithm first calculates the shortest distances which have at-most one edge in the path. Then, it calculates shortest paths with at-most 2 edges, and so on. After the ith iteration of outer loop, the shortest paths with at most i edges are calculated. There can be maximum \left | V \right | - 1 edges in any simple path, that is why the outer loop runs \left | V \right | - 1 times. The idea is, assuming that there is no negative weight cycle, if we have calculated shortest paths with at most i edges, then an iteration over all edges guarantees to give shortest path with at-most i + 1 edges.

Bellman-Ford

Floyd-Warshall Algorithm

Folyd-Warshall algorithm can finding shortest paths in a weighted graph with positive or negative edge weights (w/o negative cycles).

We initialize the result matrix same as the input matrix as a first step. Then we update the result matrix by considering all vertices as an intermediate vertex. The idea is to one by one pick all vertices and update all shortest paths which include the picked vertex as an intermediate vertex in the shortest path. When we pick vertex number k as an intermediate vertex, we already have considered vertices \left \{0, 1, 2, \cdots k - 1 \right \} as intermediate vertices. For every pair \left ( i, j \right ) of source and destination vertices respectively, there are two possible cases:

  1. k is not an intermediate vertex in shortest path from i to j. We keep the value of dist[i][j] as it is.
  2. k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j] as dist[i][k] + dist[k][j].

Floyd-Warshall Algorithm

Johnson’s Algorithm

While Floyd-Warshall algorithm is efficient for dense graphs, if the graph is sparse then an alternative all pairs shortest path strategy known as Johnson’s algorithm can be used. This algorithm basically uses Bellman-Ford algorithm to detect any negative weight cycles and then employs the technique of re-weighting the edges to allow Dijkstra’s algorithm to find the shortest paths. This algorithm can be made to run in O\left ( V^{2} \cdot \lg{V} + V \cdot E \right ):

  1. A new vertex q is added to the graph, connected by zero-weight edges to each of the other nodes.
  2. The Bellman-Ford algorithm is used, starting from the new vertex q, to find for each vertex v the minimum weight h(v) of a path from q to v. If this step detects a negative cycle, the algorithm is terminated.
  3. Next the edges of the original graph are re-weighted using the values computed by the Bellman-Ford algorithm: an edge from u to v, having length w(u, v), is given the new length w\left ( u, v \right ) + h\left ( u \right ) - h\left ( v \right ).
  4. Finally, q is removed, and Dijkstra’s algorithm is used to find the shortest paths from each node s to every other vertex in the re-weighted graph.

Leave a Reply

Your email address will not be published. Required fields are marked *

*