16

SHORTEST PATH ALGORITHMS

Question: Consider the following directed graph and apply Bellman Ford Algorithm to find
single source shortest paths.

BELLMAN FORD ALGORITHM:

Bellman ford algorithm is a single-source shortest path algorithm. This algorithm is used to find the
shortest distance from the single vertex to all the other vertices of a weighted graph. There are
various other algorithms used to find the shortest path like Dijkstra algorithm, etc. If the weighted
graph contains the negative weight values, then the Dijkstra algorithm does not confirm whether it
produces the correct answer or not. In contrast to Dijkstra algorithm, bellman ford algorithm
guarantees the correct answer even if the weighted graph contains the negative weight values.
Rule of this algorithm
1. We will go on relaxing all the edges (n - 1) times where,
2. n = number of vertices
Algorithm:
function bellmanFordAlgorithm(G, s) //G is the graph and s is the source vertex
for each vertex V in G
d[V] <- infinite // d is distance
prev[V] <- NULL // prev is previous
d[s] <- 0
for each vertex V in G
for each edge (u,v) in G
temporaryDist <- d[u] + c(u, v)
if temporaryDist < d[v]
d[v] <- temporaryDist
prev[v] <- u
for each edge (U,V) in G
If d[U] + c(U, V) < d[V}
Error: Negative Cycle Exists
return d[], previ[]

Consider the below graph:

 17

As we can observe in the above graph that some of the weights are negative. The above graph
contains 6 vertices so we will go on relaxing till the 5 vertices. Here, we will relax all the edges 5
times. The loop will iterate 5 times to get the correct answer. If the loop is iterated more than 5 times
then also the answer will be the same, i.e., there would be no change in the distance between the
vertices
Relaxing means:
If (d(u) + c(u , v) < d(v))
d(v) = d(u) + c(u , v)
To find the shortest path of the above graph, the first step is note down all the edges which are given
below:
(A, B), (A, C), (A, D), (B, E), (C, E), (D, C), (D, F), (E, F), (C, B)
Let's consider the source vertex as 'A'; therefore, the distance value at vertex A is 0 and the distance
value at all the other vertices as infinity shown as below:

Since the graph has six vertices so it will have five iterations.
First iteration
Consider the edge (A, B). Denote vertex 'A' as 'u' and vertex 'B' as 'v'. Now use the relaxing formula:
d(u) = 0
d(v) = ∞
c(u , v) = 6
Since (0 + 6) is less than ∞, so update
d(v) = d(u) + c(u,v)
d(v) = 0 + 6 = 6
Therefore, the distance of vertex B is 6.
Consider the edge (A, C). Denote vertex 'A' as 'u' and vertex 'C' as 'v'. Now use the relaxing formula:
d(u) = 0
d(v) = ∞
 18

c(u , v) = 4
Since (0 + 4) is less than ∞, so update

d(v) = 0 + 4 = 4
Therefore, the distance of vertex C is 4.
Consider the edge (A, D). Denote vertex 'A' as 'u' and vertex 'D' as 'v'. Now use the relaxing formula:
d(u) = 0
d(v) = ∞
c(u , v) = 5
Since (0 + 5) is less than ∞, so update
d(v) = d(u) + c(u,v)
d(v) = 0 + 5 = 5
Therefore, the distance of vertex D is 5.
Consider the edge (B, E). Denote vertex 'B' as 'u' and vertex 'E' as 'v'. Now use the relaxing formula:
d(u) = 6
d(v) = ∞
c(u , v) = -1
Since (6 - 1) is less than ∞, so update
d(v) = d(u) + c(u,v)
d(v) = 6 - 1= 5
Therefore, the distance of vertex E is 5.
Consider the edge (C, E). Denote vertex 'C' as 'u' and vertex 'E' as 'v'. Now use the relaxing formula:
d(u) = 4
d(v) = 5
c(u , v) = 3
Since (4 + 3) is greater than 5, so there will be no updation. The value at vertex E is 5.
Consider the edge (D, C). Denote vertex 'D' as 'u' and vertex 'C' as 'v'. Now use the relaxing formula:
d(u) = 5
d(v) = 4
c(u , v) = -2
Since (5 -2) is less than 4, so update
 19

d(v) = d(u) + c(u,v)

d(v) = 5 - 2 = 3
Therefore, the distance of vertex C is 3.
Consider the edge (D, F). Denote vertex 'D' as 'u' and vertex 'F' as 'v'. Now use the relaxing formula:
d(u) = 5
d(v) = ∞
c(u , v) = -1
Since (5 -1) is less than ∞, so update
d(v) = d(u) + c(u,v)
d(v) = 5 - 1 = 4
Therefore, the distance of vertex F is 4.
Consider the edge (E, F). Denote vertex 'E' as 'u' and vertex 'F' as 'v'. Now use the relaxing formula:
d(u) = 5
d(v) = ∞
c(u , v) = 3
Since (5 + 3) is greater than 4, so there would be no updation on the distance value of vertex F.
Consider the edge (C, B). Denote vertex 'C' as 'u' and vertex 'B' as 'v'. Now use the relaxing formula:
d(u) = 3
d(v) = 6
c(u , v) = -2
Since (3 - 2) is less than 6, so update
d(v) = d(u) + c(u,v)
d(v) = 3 - 2 = 1d(v) = d(u) + c(u,v)
Therefore, the distance of vertex B is 1.
Now the first iteration is completed. We move to the second iteration.
Second iteration:
In the second iteration, we again check all the edges. The first edge is (A, B). Since (0 + 6) is greater
than 1 so there would be no updation in the vertex B.
The next edge is (A, C). Since (0 + 4) is greater than 3 so there would be no updation in the vertex
C.
The next edge is (A, D). Since (0 + 5) equals to 5 so there would be no updation in the vertex D.
 20

The next edge is (B, E). Since (1 - 1) equals to 0 which is less than 5 so update:
d(v) = d(u) + c(u, v)
d(E) = d(B) +c(B , E)
=1-1=0
The next edge is (C, E). Since (3 + 3) equals to 6 which is greater than 5 so there would be no
updation in the vertex E.
The next edge is (D, C). Since (5 - 2) equals to 3 so there would be no updation in the vertex C.
The next edge is (D, F). Since (5 - 1) equals to 4 so there would be no updation in the vertex F.
The next edge is (E, F). Since (5 + 3) equals to 8 which is greater than 4 so there would be no
updation in the vertex F.
The next edge is (C, B). Since (3 - 2) equals to 1` so there would be no updation in the vertex B.

Third iteration
We will perform the same steps as we did in the previous iterations. We will observe that there will
be no updation in the distance of vertices.
The following are the distances of the matrix:
A: 0
B: 1
C: 3
D: 5
E: 0
F: 3

Time Complexity
The time complexity of Bellman ford algorithm would be O(E|V| - 1).
 21

Question: Consider the following directed graph and apply Dijkstra algorithm to find single
source shortest paths.

Dijkstra algorithm is a single-source shortest path algorithm. Here, single-source means

that only one source is given, and we have to find the shortest path from the source to all
the nodes.

Let's understand the working of Dijkstra's algorithm. Consider the below graph.

First, we have to consider any vertex as a source vertex. Suppose we consider vertex 0 as a
source vertex.

Here we assume that 0 as a source vertex, and distance to all the other vertices is infinity.
Initially, we do not know the distances. First, we will find out the vertices which are directly
connected to the vertex 0. As we can observe in the above graph that two vertices are
directly connected to vertex 0.
55.8M
1K

Java Try Catch

Let's assume that the vertex 0 is represented by 'x' and the vertex 1 is represented by 'y'.
The distance between the vertices can be calculated by using the below formula:
d(x, y) = d(x) + c(x, y) < d(y)
= (0 + 4) < ∞
=4<∞
 22

Since 4<∞ so we will update d(v) from ∞ to 4.

Therefore, we come to the conclusion that the formula for calculating the distance between
the vertices:

{if( d(u) + c(u, v) < d(v))

d(v) = d(u) +c(u, v) }

Now we consider vertex 0 same as 'x' and vertex 4 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (0 + 8) < ∞
=8<∞

Therefore, the value of d(y) is 8. We replace the infinity value of vertices 1 and 4 with the
values 4 and 8 respectively. Now, we have found the shortest path from the vertex 0 to 1
and 0 to 4. Therefore, vertex 0 is selected. Now, we will compare all the vertices except the
vertex 0. Since vertex 1 has the lowest value, i.e., 4; therefore, vertex 1 is selected.

Since vertex 1 is selected, so we consider the path from 1 to 2, and 1 to 4. We will not
consider the path from 1 to 0 as the vertex 0 is already selected.

First, we calculate the distance between the vertex 1 and 2. Consider the vertex 1 as 'x', and
the vertex 2 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (4 + 8) < ∞
= 12 < ∞

Since 12<∞ so we will update d(2) from ∞ to 12.

Now, we calculate the distance between the vertex 1 and vertex 4. Consider the vertex 1 as
'x' and the vertex 4 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (4 + 11) < 8
= 15 < 8

Since 15 is not less than 8, we will not update the value d(4) from 8 to 12.

Till now, two nodes have been selected, i.e., 0 and 1. Now we have to compare the nodes
except the node 0 and 1. The node 4 has the minimum distance, i.e., 8. Therefore, vertex 4
is selected.
 23

Since vertex 4 is selected, so we will consider all the direct paths from the vertex 4. The
direct paths from vertex 4 are 4 to 0, 4 to 1, 4 to 8, and 4 to 5. Since the vertices 0 and 1
have already been selected so we will not consider the vertices 0 and 1. We will consider
only two vertices, i.e., 8 and 5.

First, we consider the vertex 8. First, we calculate the distance between the vertex 4 and 8.
Consider the vertex 4 as 'x', and the vertex 8 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (8 + 7) < ∞
= 15 < ∞

Since 15 is less than the infinity so we update d(8) from infinity to 15.

Now, we consider the vertex 5. First, we calculate the distance between the vertex 4 and 5.
Consider the vertex 4 as 'x', and the vertex 5 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (8 + 1) < ∞
=9<∞

Since 5 is less than the infinity, we update d(5) from infinity to 9.

Till now, three nodes have been selected, i.e., 0, 1, and 4. Now we have to compare the
nodes except the nodes 0, 1 and 4. The node 5 has the minimum value, i.e., 9. Therefore,
vertex 5 is selected.

Since the vertex 5 is selected, so we will consider all the direct paths from vertex 5. The
direct paths from vertex 5 are 5 to 8, and 5 to 6.

First, we consider the vertex 8. First, we calculate the distance between the vertex 5 and 8.
Consider the vertex 5 as 'x', and the vertex 8 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (9 + 15) < 15
= 24 < 15

Since 24 is not less than 15 so we will not update the value d(8) from 15 to 24.

Now, we consider the vertex 6. First, we calculate the distance between the vertex 5 and 6.
Consider the vertex 5 as 'x', and the vertex 6 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

 24

= (9 + 2) < ∞</p>
= 11 < ∞

Since 11 is less than infinity, we update d(6) from infinity to 11.

Till now, nodes 0, 1, 4 and 5 have been selected. We will compare the nodes except the
selected nodes. The node 6 has the lowest value as compared to other nodes. Therefore,
vertex 6 is selected.

Since vertex 6 is selected, we consider all the direct paths from vertex 6. The direct paths
from vertex 6 are 6 to 2, 6 to 3, and 6 to 7.

First, we consider the vertex 2. Consider the vertex 6 as 'x', and the vertex 2 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (11 + 4) < 12
= 15 < 12

Since 15 is not less than 12, we will not update d(2) from 12 to 15

Now we consider the vertex 3. Consider the vertex 6 as 'x', and the vertex 3 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (11 + 14) < ∞
= 25 < ∞

Since 25 is less than ∞, so we will update d(3) from ∞ to 25.

Now we consider the vertex 7. Consider the vertex 6 as 'x', and the vertex 7 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (11 + 10) < ∞
= 22 < ∞

Since 22 is less than ∞ so, we will update d(7) from ∞ to 22.

Till now, nodes 0, 1, 4, 5, and 6 have been selected. Now we have to compare all the
unvisited nodes, i.e., 2, 3, 7, and 8. Since node 2 has the minimum value, i.e., 12 among all
the other unvisited nodes. Therefore, node 2 is selected.

Since node 2 is selected, so we consider all the direct paths from node 2. The direct paths
from node 2 are 2 to 8, 2 to 6, and 2 to 3.
 25

First, we consider the vertex 8. Consider the vertex 2 as 'x' and 8 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (12 + 2) < 15
= 14 < 15

Since 14 is less than 15, we will update d(8) from 15 to 14.

Now, we consider the vertex 6. Consider the vertex 2 as 'x' and 6 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (12 + 4) < 11
= 16 < 11

Since 16 is not less than 11 so we will not update d(6) from 11 to 16.

Now, we consider the vertex 3. Consider the vertex 2 as 'x' and 3 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (12 + 7) < 25
= 19 < 25

Since 19 is less than 25, we will update d(3) from 25 to 19.

Till now, nodes 0, 1, 2, 4, 5, and 6 have been selected. We compare all the unvisited nodes,
i.e., 3, 7, and 8. Among nodes 3, 7, and 8, node 8 has the minimum value. The nodes which
are directly connected to node 8 are 2, 4, and 5. Since all the directly connected nodes are
selected so we will not consider any node for the updation.

The unvisited nodes are 3 and 7. Among the nodes 3 and 7, node 3 has the minimum value,
i.e., 19. Therefore, the node 3 is selected. The nodes which are directly connected to the
node 3 are 2, 6, and 7. Since the nodes 2 and 6 have been selected so we will consider
these two nodes.

Now, we consider the vertex 7. Consider the vertex 3 as 'x' and 7 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (19 + 9) < 21
= 28 < 21

Since 28 is not less than 21, so we will not update d(7) from 28 to 21.
 26

LET'S CONSIDER THE DIRECTED GRAPH :

Here, we consider A as a source vertex. A vertex is a source vertex so entry is filled with 0
while other vertices filled with ∞. The distance from source vertex to source vertex is 0, and
the distance from the source vertex to other vertices is ∞.

We will solve this problem using the below table:

A B C D E

∞ ∞ ∞ ∞ ∞

Since 0 is the minimum value in the above table, so we select vertex A and added in the
second row shown as below:

A B C D E

A 0 ∞ ∞ ∞ ∞

As we can observe in the above graph that there are two vertices directly connected to the
vertex A, i.e., B and C. The vertex A is not directly connected to the vertex E, i.e., the edge
is from E to A. Here we can calculate the two distances, i.e., from A to B and A to C. The
same formula will be used as in the previous problem.

1. If(d(x) + c(x, y) < d(y))

2. Then we update d(y) = d(x) + c(x, y)
 27
A B C D E

A 0 ∞ ∞ ∞ ∞

10 5 ∞ ∞
As we can observe in the third row that 5 is the lowest value so vertex C will be added in
the third row.

We have calculated the distance of vertices B and C from A. Now we will compare the
vertices to find the vertex with the lowest value. Since the vertex C has the minimum value,
i.e., 5 so vertex C will be selected.

Since the vertex C is selected, so we consider all the direct paths from the vertex C. The
direct paths from the vertex C are C to B, C to D, and C to E.

First, we consider the vertex B. We calculate the distance from C to B. Consider vertex C as
'x' and vertex B as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (5 + 3) < ∞
=8<∞

Since 8 is less than the infinity so we update d(B) from ∞ to 8. Now the new row will be inserted
in which value 8 will be added under the B column.

A B C D E

A 0 ∞ ∞ ∞ ∞

10 5 ∞ ∞

We consider the vertex D. We calculate the distance from C to D. Consider vertex C as 'x' and
vertex D as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (5 + 9) < ∞
= 14 < ∞

Since 14 is less than the infinity so we update d(D) from ∞ to 14. The value 14 will be added
under the D column.

A B C D E
 28

A 0 ∞ ∞ ∞ ∞

C 10 5 ∞ ∞

8 14

We consider the vertex E. We calculate the distance from C to E. Consider vertex C as 'x' and
vertex E as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (5 + 2) < ∞
=7<∞

Since 14 is less than the infinity so we update d(D) from ∞ to 14. The value 14 will be added
under the D column.

A B C D E

A 0 ∞ ∞ ∞ ∞

C 10 5 ∞ ∞

8 14 7

As we can observe in the above table that 7 is the minimum value among 8, 14, and 7. Therefore,
the vertex E is added on the left as shown in the below table:

A B C D E

A 0 ∞ ∞ ∞ ∞

C 10 5 ∞ ∞

E 8 14 7

The vertex E is selected so we consider all the direct paths from the vertex E. The direct paths
from the vertex E are E to A and E to D. Since the vertex A is selected, so we will not consider the
path from E to A.

Consider the path from E to D.

d(x, y) = d(x) + c(x, y) < d(y)

= (7 + 6) < 14
 29

= 13 < 14
Since 13 is less than the infinity so we update d(D) from ∞ to 13. The value 13 will be added
under the D column.

A B C D E

A 0 ∞ ∞ ∞ ∞

C 10 5 ∞ ∞

E 8 14 7

B 8 13

The value 8 is minimum among 8 and 13. Therefore, vertex B is selected. The direct path from B
is B to D.

A B C D E

A 0 ∞ ∞ ∞ ∞

C 10 5 ∞ ∞

E 8 14 7

B 8 13

D 9

d(x, y) = d(x) + c(x, y) < d(y)

= (8 + 1) < 13
= 9 < 13

Since 9 is less than 13 so we update d(D) from 13 to 9. The value 9 will be added under the D
column.
 30

Dynamic Programming - All-Pairs Shortest Paths: Shortest Paths and Matrix Multiplication

Question: Consider the following directed graph and apply Floyd-Warshall Algorithm to
find all source shortest paths.

Floyd-Warshall Algorithm is an algorithm for finding the shortest path between all the pairs of
vertices in a weighted graph. This algorithm works for both the directed and undirected weighted
graphs. But, it does not work for the graphs with negative cycles (where the sum of the edges in a
cycle is negative).
Floyd-Warhshall algorithm is also called as Floyd's algorithm, Roy-Floyd algorithm, Roy-
Warshall algorithm, or WFI algorithm.

This algorithm follows the dynamic programming approach to find the shortest paths.
How Floyd-Warshall Algorithm Works?
Let the given graph be:

Follow the steps below to find the shortest path between all the pairs of vertices.

Create a matrix A0 of dimension n*n where n is the number of vertices. The row and the column
are indexed as i and j respectively. i and j are the vertices of the graph.

Each cell A[i][j] is filled with the distance from the ith vertex to the jth vertex. If there is no path
from ith vertex to jth vertex, the cell is left as infinity.
 31

2. Now, create a matrix A1 using matrix A0. The elements in the first column and the first row are
left as they are. The remaining cells are filled in the following way.

Let k be the intermediate vertex in the shortest path from source to destination. In this step, k is
the first vertex. A[i][j] is filled with (A[i][k] + A[k][j]) if (A[i][j] > A[i][k] + A[k][j]).

That is, if the direct distance from the source to the destination is greater than the path through the
vertex k, then the cell is filled with A[i][k] + A[k][j].

In this step, k is vertex 1. We calculate the distance from source vertex to destination vertex
through this vertex k.

For example: For A1[2, 4], the direct distance from vertex 2 to 4 is 4 and the sum of the distance
from vertex 2 to 4 through vertex (ie. from vertex 2 to 1 and from vertex 1 to 4) is 7. Since 4 <
7, A0[2, 4] is filled with 4.

3. Similarly, A2 is created using A1. The elements in the second column and the second row are
left as they are.

In this step, k is the second vertex (i.e. vertex 2). The remaining steps are the same as in step 2.

4. Similarly, A3 and A4 is also created.

 32

5. A4 gives the shortest path between each pair of vertices.