2|DAA- Assignment -All pairs of shortest paths

All pairs of shortest paths

Sl no. Table of contents

01. Introduction
3|DAA- Assignment -All pairs of shortest paths

Floyd-Warshall Algorithm
02.

i. History of Floyd-Warshall Algorithm

ii. Working of Floyd-Warshall Algorithm

iii. Implementation of Floyd-Warshall Algorithm

iv. Advantages of Floyd-Warshall Algorithm

v. Disadvantages of Floyd-Warshall Algorithm

vi. Applications of Floyd-Warshall Algorithm

03. Johnson’s Algorithm

4|DAA- Assignment -All pairs of shortest paths

All pairs of shortest paths

Introduction:
aim to figure out the shortest path from each vertex v to every other u. Storing all the
paths explicitly can be very memory expensive indeed, as we need one spanning tree
for each vertex. This is often impractical regarding memory consumption, so these are
generally considered as all pairs-shortest distance problems, which aim to find just
the distance from each to each node to another. We usually want the output in
tabular form: the entry in u's row and v's column should be the weight of the shortest
path from u to v.

Algorithm Cost

Matrix Multiplication O (V3 logV)

Floyd-Warshall O (V3)

Johnson O (V2 log?V+VE)

Three approaches for improvement:

Unlike the single-source algorithms, which assume an adjacency list representation of

the graph, most of the algorithm uses an adjacency matrix representation. (Johnson's
Algorithm for sparse graphs uses adjacency lists.) The input is a n x n matrix W
representing the edge weights of an n-vertex directed graph G = (V, E). That is, W =
(wij), where
5|DAA- Assignment -All pairs of shortest paths

Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a dynamic programming algorithm used to discover

the shortest paths in a weighted graph, which includes negative weight cycles. The
algorithm works with the aid of computing the shortest direction between every pair
of vertices within the graph, the usage of a matrix of intermediate vertices to keep
music of the exceptional-recognized route thus far.

I. History of Floyd-Warshall algorithm:

The Floyd-Warshall set of rules was advanced independently via Robert Floyd and
Stephen Warshall in 1962. Robert Floyd turned into a mathematician and computer
scientist at IBM's Thomas J. Watson Research Center, whilst Stephen Warshall became
a computer scientist at the University of California, Berkeley. The algorithm was
originally developed for use inside the field of operations research, where it turned
into used to solve the all-pairs shortest direction problem in directed graphs with
tremendous or negative side weights. The problem become of outstanding hobby in
operations research, as it has many applications in transportation, conversation, and
logistics.

Floyd first presented the set of rules in a technical record titled "Algorithm 97:
Shortest Path" in 1962. Warshall independently discovered the set of rules quickly
afterwards and posted it in his personal technical document, "A Theorem on Boolean
Matrices". The algorithm has on account that emerged as a cornerstone of pc
technology and is broadly used in lots of regions of studies and enterprise. Its
capability to correctly find the shortest paths between all pairs of vertices in a graph,
including those with terrible side weights, makes it a treasured tool for solving an
extensive range of optimization problems.

II. Working of Floyd-Warshall Algorithm:

The set of rules works as follows:
6|DAA- Assignment -All pairs of shortest paths

 Initialize a distance matrix D wherein D[i][j] represents the shortest distance

between vertex i and vertex j.
 Set the diagonal entries of the matrix to 0, and all other entries to infinity.
 For every area (u,v) inside the graph, replace the gap matrix to mirror the
weight of the brink: D[u][v] = weight(u,v).
 For every vertex okay in the graph, bear in mind all pairs of vertices (i,j) and
check if the path from i to j through k is shorter than the current best path. If it
is, update the gap matrix: D[i][j] = min(D[i][j], D[i][k] D[k][j]).
 After all iterations, the matrix D will contain the shortest course distances
between all pairs of vertices.
Example:
Floyd-Warshall is an algorithm used to locate the shortest course between all pairs of
vertices in a weighted graph. It works by means of keeping a matrix of distances
between each pair of vertices and updating this matrix iteratively till the shortest
paths are discovered.
Let's see at an example to illustrate how the Floyd-Warshall algorithm works:

Consider the following weighted graph:-

Figure: A Weighted Graph

In this graph, the vertices are represented by letters (A, B, C, D), and the numbers on
the edges represent the weights of those edges.
To follow the Floyd-Warshall algorithm to this graph, we start by way of initializing a
matrix of distances among every pair of vertices. If two vertices are immediately
7|DAA- Assignment -All pairs of shortest paths

related by using a side, their distance is the load of that edge. If there may be no
direct edge among vertices, their distance is infinite.

In the first iteration of the set of rules, we keep in mind the possibility of the usage of
vertex 1 (A) as an intermediate vertex in paths among all pairs of vertices. If the space
from vertex 1 to vertex 2 plus the space from vertex 2 to vertex three is much less
than the present-day distance from vertex 1 to vertex three, then we replace the
matrix with this new distance. We try this for each possible pair of vertices .

In the second iteration, we recollect the possibility to use of vertex 2 (B) as an

intermediate vertex in paths among all pairs of vertices. We replace the matrix in the
same manner as earlier before.

In the third iteration, we consider the possibility of using vertex 3 (C) as an

intermediate vertex in paths between all pairs of vertices.
8|DAA- Assignment -All pairs of shortest paths

Finally, in the fourth and final iteration, we consider the possibility of using vertex 4
(D) as an intermediate vertex in paths between all pairs of vertices.

After the fourth iteration, we have got the shortest path between every pair of vertices
in the graph. For example, the shortest path from vertex A to vertex D is 4, which is
the value in the matrix at row A and column D.

After the fourth iteration, we have got the shortest path between every pair of vertices
in the graph. For example, the shortest path from vertex A to vertex D is 4, which is
the value in the matrix at row A and column D.

III. Implementation of Floyd-Warshall Algorithm

ALGORITHM : FLOYD(n, cost, D)
//Purpose: To implement Floyd's algorithm for all-pairs shortest paths problem
//Input: Cost adjacency matrix cost of size n*n
//Output: Shortest distance matrix of size n*n
for i=0 to n-1 do
for j=0 to n-1 do
9|DAA- Assignment -All pairs of shortest paths

D[i,j]=cost[i,j]
end for
end for

for k=0 to n-1 do

for k=0 to n-1 do
for i=0 to n-1 do
D[i,j]=min(D[i,j],D[i,k]+D[k,j])
end for
end for
end for

Obtaining time complexity for Floyd’s Algorithm:

Analysis: The time efficiency of Floyd’s Algorithm can be shown below as:

Step 1: The parameter to be considered is n which represent the size of input.

Step 2: The basic operation is the comparison statement in the innermost loop.
Step 3: The total number of times the basic operation is executed can be obtained as
10 | D A A - A s s i g n m e n t - A l l p a i r s o f s h o r t e s t p a t h s

shown below:
for k=0 to n-1 do
for k=0 to n-1 do
for i=0 to n-1 do
D[i,j]=min(D[i,j],D[i,k]+D[k,j])

n =1 n =1 n=1
f(n) =∑ ❑ ∑ ∑ 1
k=0 i=0 j=0

n =1 n=1
=∑ ∑ n−1−0+1
k=0 i =0

n =1 n =1
=∑ ❑ ∑ n
k=0 i=0

n =1 n=1
=∑ n ∑ 1
k=0 i =0

n =1
= ∑ n(n−1−0+1)
k=0

n =1
=∑ n ¿ ¿)
k=0

n =1
=∑ n
2

k=0

=n2 (n−1−0+1 ¿

= n3

So the time complexity of Warshall’s algorithm is given by Θ(n^2)

IV. Advantages of the Floyd-Warshall algorithm include:

 It can discover the shortest direction between all pairs of vertices in a weighted
graph, such as graphs with negative edge weights.
 It is an easy and smooth-to-put algorithm, making it accessible to developers of
all skill ranges.
 It is appropriate for both dense and sparse graphs.
 It has a time complexity of O(N^3), that is relatively efficient for most real-
international applications.
11 | D A A - A s s i g n m e n t - A l l p a i r s o f s h o r t e s t p a t h s

 It can be used to discover negative weight cycles in a graph.

V. Disadvantages of the Floyd-Warshall set of rules include:

 It calls for a matrix of size N^2 to store the intermediate results, which may be
prohibitively large for extremely large graphs.
 It is not the maximum green set of rules for fixing the all-pairs shortest path
hassle in sure types of graphs, inclusive of sparse graphs or graphs with non-
bad part weights.
 It won't be suitable for real-time packages or packages with strict reminiscence
constraints, as it is able to take a long term to compute the shortest paths in
very huge graphs.
 It can be less intuitive than different algorithms, which include Dijkstra's
algorithm, or the Bellman-Ford set of rules, making it more difficult to
understand for some builders.

VI. Applications of Floyd Warshall Algorithm:

The Floyd-Warshall algorithm is a dynamic programming algorithm used for finding
the shortest course among all pairs of vertices in a weighted graph. Here are some of
the programs of the Floyd- Warshall algorithm:

1. Routing Algorithms: The Floyd-Warshall algorithm is broadly utilized in routing

algorithms, along with within the OSPF (Open Shortest Path First) protocol
utilized in Internet routing. It can help decide the shortest route among two
nodes in a network and is useful in locating the least congested path.
2. Airline Networks: The Floyd-Warshall set of rules can also be utilized in airline
networks to locate the shortest path between two cities with the lowest cost. It
can assist airways plan their routes and limit fuel charges.
3. Traffic Networks: The algorithm is used to find the shortest path between
points in a visitors' network. It can help reduce congestion and improve the go
with the flow of visitors in city areas.
4. Computer Networks: The Floyd-Warshall algorithm is likewise utilized in laptop
networks to decide the shortest course between hosts in a network. It can assist
in minimizing community latency and improve community overall performance.
5. Game Development: The set of rules may be used in game development to find
the shortest direction among two items in a sport world. It is beneficial in
12 | D A A - A s s i g n m e n t - A l l p a i r s o f s h o r t e s t p a t h s

games in which the participant desires to navigate through complex

surroundings, together with a maze or a metropolis.
These are only some of the numerous applications of the Floyd-Warshall algorithm. It
is a powerful algorithm that can be applied in an extensive variety of fields to remedy
a whole lot of troubles.

Johnson's Algorithm
The problem is to find the shortest path between every pair of vertices in a given
weighted directed graph and weight may be negative. Using Johnson's Algorithm, we
can find all pairs shortest path in O (V2 log ? V+VE ) time. Johnson's Algorithm uses
both Dijkstra's Algorithm and Bellman-Ford Algorithm.

Johnson's Algorithm uses the technique of "reweighting." If all edge weights w in a

graph G = (V, E) are nonnegative, we can find the shortest paths between all pairs of
vertices by running Dijkstra's Algorithm once from each vertex. If G has negative -
weight edges, we compute a new - set of non - negative edge weights that allows us

to use the same method. The new set of edges weight w must satisfy two essential
properties:

For all pair of vertices u, v ∈ V, the shortest path from u to v using weight function w
is also the shortest path from u to v using weight function w.
For all edges (u, v), the new weight w (u, v) is nonnegative.
Given a weighted, directed graph G = (V, E) with weight function w: E→R and let h:
v→R be any function mapping vertices to a real number.

For each edge (u, v) ∈ E define

Johnson's Algorithm
13 | D A A - A s s i g n m e n t - A l l p a i r s o f s h o r t e s t p a t h s

Where h (u) = label of u

h (v) = label of v

JOHNSON (G)
1. Compute G' where V [G'] = V[G] ∪ {S} and
E [G'] = E [G] ∪ {(s, v): v ∈ V [G] }

2. If BELLMAN-FORD (G',w, s) = FALSE

then "input graph contains a negative weight cycle"

for each vertex v ∈ V [G']

else

do h (v) ← δ(s, v)

for each edge (u, v) ∈ E[G']

Computed by Bellman-Ford algorithm

for each edge u ∈ V [G]

do w (u, v) ← w (u, v) + h (u) - h (v)

δ (u, v) for all v ∈ V [G]

do run DIJKSTRA (G, w, u) to compute

for each vertex v ∈ V [G]

do duv← δ (u, v) + h (v) - h (u)
Return D.

Example:
14 | D A A - A s s i g n m e n t - A l l p a i r s o f s h o r t e s t p a t h s

Step1: Take any source vertex's' outside the graph and make distance from 's' to
every vertex '0'.

Step2: Apply Bellman-Ford Algorithm and calculate minimum weight on each vertex

Step3: w (a, b) = w (a, b) + h (a) - h (b)

= -3 + (-1) - (-4)
=0

w (b, a) = w (b, a) + h (b) - h (a)

= 5 + (-4) - (-1)
=2
w (b, c) = w (b, c) + h (b) - h (c)
w (b, c) = 3 + (-4) - (-1)
=0
w (c, a) = w (c, a) + h (c) - h (a)
w (c, a) = 1 + (-1) - (-1)
=1
w (d, c) = w (d, c) + h (d) - h (c)
w (d, c) = 4 + 0 - (-1)
15 | D A A - A s s i g n m e n t - A l l p a i r s o f s h o r t e s t p a t h s

=5
w (d, a) = w (d, a) + h (d) - h (a)

w (d, a) = -1 + 0 - (-1)
=0
w (a, d) = w (a, d) + h (a) - h (d)
w (a, d) = 2 + (-1) - 0 = 1

Step 4: Now all edge weights are positive and now we can apply Dijkstra's Algorithm
on each vertex and make a matrix corresponds to each vertex in a graph.

Case 1: 'a' as a source vertex

Case 2: 'b' as a source vertex

16 | D A A - A s s i g n m e n t - A l l p a i r s o f s h o r t e s t p a t h s

Case 3: 'c' as a source vertex

17 | D A A - A s s i g n m e n t - A l l p a i r s o f s h o r t e s t p a t h s

Case4:'d' as source vertex

Step5:
18 | D A A - A s s i g n m e n t - A l l p a i r s o f s h o r t e s t p a t h s

duv ← δ (u, v) + h (v) - h (u)

d (a, a) = 0 + (-1) - (-1) = 0
d (a, b) = 0 + (-4) - (-1) = -3
d (a, c) = 0 + (-1) - (-1) = 0
d (a, d) = 1 + (0) - (-1) = 2
d (b, a) = 1 + (-1) - (-4) = 4
d (b, b) = 0 + (-4) - (-4) = 0
d (c, a) = 1 + (-1) - (-1) = 1
d (c, b) = 1 + (-4) - (-1) = -2
d (c, c) = 0
d (c, d) = 2 + (0) - (-1) = 3
d (d, a) = 0 + (-1) - (0) = -1
d (d, b) = 0 + (-4) - (0) = -4
d (d, c) = 0 + (-1) - (0) = -1
d (d, d) = 0