40 Shortest Path Algorithm II

T.V. Geetha

Welcome to the e-PG Pathshala Lecture Series on Data Structures. In this module we will again discuss about shortest path algorithms.

Learning Objectives

The learning objectives of the module are as follows:

•  To explain the Bellman-Ford algorithm  for Single-source shortest paths

•  To illustrate the Bellman-Ford Algorithm with an example

•  To discuss the Floyd-Warshall Algorithm for All-Pairs Shortest Paths

40.1 Recap

Before we discuss other shortest path algorithms let us recall some basic procedures we used for Dijkstra’s algorithm. For a graph G (V,E), the single-source shortest path algorithms with the start vertex s, keeps track of d[v] which indicates the shortest path weight from source to vertex v and p[v] which indicates the predecessor u of v in the shortest path. Algorithms keep track of d[v], p[v]. They are initialized as follows:

40.2 Single-source shortest paths

Two classic algorithms to solve single-source shortest path problem are Dijkstra’s algorithm and Bellman-Ford algorithm. The Dijkstra’s algorithm has been already discussed in the previous module and in this module we will discuss in detail the Bellman-Ford algorithm.

40.2.1 Dijkstra and Negative-Weight Edges

Dijkstra algorithm is a greedy algorithm where it adds vertices by increasing distance but is faster than Bellman-Ford algorithm. However, it works only when the weights are all non-negative. If a node with a negative incident edge were to be added late to the cloud, it could mess up distances for vertices already in the cloud. For example in Figure 40.1 C’s true distance is 1, but it is already in the cloud with d(C)=5.

40.3 Bellman-Ford Algorithm

Bellman-Ford algorithm is a dynamic programming algorithm that solves the single source shortest path problem. The main advantage of the algorithm is that it works even when some weights are negative. Single-source shortest path problem computes δ(s, v) and p[v] for all v Î V. The algorithm allows negative edge weights – can detect negative cycles. The basic idea of this algorithm is as follows.

• Each edge is relaxed |V–1| times by making |V -1| passes over the whole edge set.
• To make sure that each edge is relaxed exactly |V – 1| times, it puts the edges in an unordered list and goes over the list |V – 1| times.

40.5  Bellman-Ford algorithm: Example 1

The example has been adopted from

www.cs.bilkent.edu.tr/~atat/502/SingleSourceSP.ppt

40.6 Bellman-Ford algorithm: Dynamic Programming

For each node v, find the length of the shortest path to any node t that uses at most 1 edge, or write down ∞ if there is no such path. If v = t we get 0; if (v, t) ∈ E then we get len(v, t); else just put down ∞. Now, suppose for all v we have solved for length of the shortest path to t that uses i − 1 or fewer edges.

We can use the above to solve for the shortest path that uses i or fewer edges. The shortest path from v to t that uses i or fewer edges will first go to some neighbor x of v, and then take the shortest path from x to t that uses i−1 or fewer edges, which we’ve already solved for. So, we just need to take the minimum over all neighbors x of v. At most i = n − 1 edges need to be processed to obtain the answer. The main observation made here are as follows. (i) If there is a negative cycle, then there is no solution. Because adding this cycle again can always produces a less weighted path. (ii)  If there is no negative cycle, a shortest path has at most |V|-1 edges. The basic idea behind solving this algorithm using dynamic programming is that for all the paths have at most 0 edge, find all the shortest paths, for all the paths have at most 1 edge, find all the shortest paths and so on and finally for all the paths have at most |V|-1 edge, find all the shortest paths. The algorithm for the above is given below:

Bellman-Ford pseudocode:

initialize d[v][0] = infinity for v != t. d[t][i]=0 for all i.

for i=1 to n-1:

for each v != t:

d[v][i] = min

(v,x)2E

(len(v,x) + d[x][i-1])

For each v, output d[v][n-1].

40.6.1 Bellman-Ford algorithm: Example 2

Based on the above idea, the shortest path from node 1 to other nodes of Figure 40.4 is discovered. The total number of nodes is 3 and hence the process repeats 3 times. First the shortest paths with 0-edge are discovered from vertex 1 to 1, 1 to 2 and 1 to 3. The path weights for 1 to 1, 1 to 2 and 1 to 3 are 0, ∞ and ∞ respectively (Figure 40.4).

Finally, the shortest paths with 2-edges are discovered from vertex 1 to 1, 1 to 2 and 1 to 3. The path weights for 1 to 1, 1 to 2 and 1 to 3 are 0, 10 and 11 respectively. The path from 1 to 3 changes from 20 to 10 since the 2-edge path is shorter than the 1-edge path (Figure 40.6).

40.7 Bellman-Ford algorithm- Walkthrough

Let us consider one more example for the graph given in Figure 40.7 (a). The same procedure mentioned above is repeated to find the shortest path from vertex 1.

Now we find the shortest path from 1 with 1 edge which is 1-2 and 1-4. Hence the d value of 2 changes from ¥ to 6 and that of 4 changes from ¥ to 7 (Figure 40.7 (b)).

Now we find the shortest path from 1 with 2 edges which is 1-2-3 (d =11) and 1-4-3 (d=4). Hence the d value of 3 is 11/4. The 2 edge path to 5 is 1-2-5 and so d value of 5 is ¥/2 (Figure 40.7 (c)).

The shortest paths with negative cycle is shown in Figure 40.7 (f). The shortest path from 1 to 5 is 1-4-3-2-5 and its weight is -2.

40.8 All-Pair Shortest Path Algorithm

It aims at computing the shortest paths between all pairs of vertices in a directed graph G = (V, E). Each edge e (u, v) has a weight w which is a real number (i.e. Weight function w : E → R). The output is an n× n matrix of shortest-path distances δ(u, v). For example, let us consider graph in Figure 40.8. The all-pair shortest path algorithm finds the shortest path from vertex 1 to all the other vertices, vertex 2 to all other vertices and so on.

The possible solutions for All-Pairs Shortest Paths is to run BELLMAN-FORD once from each vertex. The time complexity is O(V2E), which is O(V4) if the graph is dense (E = Q(V2)). If there are no negative-weight edges, we could run Dijkstra’s algorithm once from each vertex. The time complexity is then O(VElogV) with binary heap and O(V3logV) if the graph is dense. Assume G=(V,E) is a graph such that c[v,w] ³ 0, where C is the matrix of edge costs. Find for each pair (v,w), the shortest path from v to w. In other words we need to find the matrix of shortest paths . Certainly this is a generalization of Dijkstra’s. A dedicated All-Pairs Shortest Paths algorithm is called Floyd-Warshall Algorithm which is discussed in detail below.

40.9 Floyd-Warshall Algorithm

Floyd-Warshall Algorithm uses nxn matrix A to compute the lengths of the shortest paths using a dynamic programming technique.

Initially, let Let A[i,j] = c[i,j] for all i,j & i¹j where c[i, j] is the cost matrix of the edges, i and j are vertices.

If (i,j) is not an edge, set A[i,j]=infinity and A[i,i]=0 .

The main idea is to find Ak[i,j] = min (Ak-1[i,j] , Ak-1[i,k]+ Ak-1[k,j]) where Ak is the matrix after k-th iteration and path from i to j does not pass through a vertex higher than k.

To find the shortest paths that uses 2 or fewer edges find A2, where multiplication is defined as minimum of sums instead sum of products. That is (A2)ij = min{ Aik + Akj | k =1..n} . This operation is O(n3). Using A2 you can find A4 and then A8 and so on. Therefore to find An we need log n operations. Hence the time complexity of this algorithm is O(log n* n3). The following is the pseudo code of Floyd-Warshall Implementation.

Initialize A[i,j] = C[i,j]

Initialize all A[i,i] = 0

for k from 1 to n

for i from 1 to n

for j from 1 to n

if (A[i,j] > A[i,k]+A[k,j])

A[i,j] = A[i,k]+A[k,j];

Summary

• Explained the Bellman-Ford algorithm for Single -source shortest paths
• Illustrated the Bellman-Ford Algorithm with an example
• Discussed the Floyd-Warshall Algorithm for All-Pairs Shortest Paths