Tag: all pair shortest path

Floyd-Warshall Algorithm | Shortest Path Algorithm

Floyd-Warshall Algorithm-

 

  • Floyd-Warshall Algorithm is an algorithm for solving All Pairs Shortest path problem which gives the shortest path between every pair of vertices of the given graph.
  • Floyd-Warshall Algorithm is an example of dynamic programming.
  • The main advantage of Floyd-Warshall Algorithm is that it is extremely simple and easy to implement.

 

Algorithm-

 

Create a |V| x |V| matrix          // It represents the distance between every pair of vertices as given

For each cell (i,j) in M do-

if i = = j

M[ i ][ j ] = 0                 // For all diagonal elements, value = 0

if (i , j) is an edge in E

M[ i ][ j ] = weight(i,j)    // If there exists a direct edge between the vertices, value = weight of edge

else

M[ i ][ j ] = infinity         // If there is no direct edge between the vertices, value = 

for k from 1 to |V|

for i from 1 to |V|

for j from 1 to |V|

if M[ i ][ j ] > M[ i ][ k ] + M[ k ][ j ]
M[ i ][ j ] = M[ i ][ k ] + M[ k ][ j ]

 

Time Complexity-

 

  • Floyd Warshall Algorithm consists of three loops over all nodes.
  • The inner most loop consists of only operations of a constant complexity.
  • Hence, the asymptotic complexity of Floyd-Warshall algorithm is O(n3), where n is the number of nodes in the given graph.

 

When Floyd- Warshall Algorithm is used?

 

  • Floyd-Warshall Algorithm is best suited for dense graphs since its complexity depends only on the number of vertices in the graph.
  • For sparse graphs, Johnson’s Algorithm is more suitable.

 

PRACTICE PROBLEM BASED ON FLOYD-WARSHALL ALGORITHM-

 

Problem-

Consider the following directed weighted graph-

 

 

Using Floyd-Warshall Algorithm, find the shortest path distance between every pair of vertices.

 

Solution-

 

Step-01:

 

  • Remove all the self loops and parallel edges (keeping the edge with lowest weight) from the graph if any.
  • In our case, we don’t have any self edge and parallel edge.

 

Step-02:

 

Now, write the initial distance matrix representing the distance between every pair of vertices as mentioned in the given graph in the form of weights.

 

  • For diagonal elements (representing self-loops), value = 0
  • For vertices having a direct edge between them, value = weight of that edge
  • For vertices having no direct edges between them, value = 

 

 

Step-03:

 

From step-03, we will start our actual solution.

 

NOTE

  • Since, we have total 4 vertices in our given graph, so we will have total 4 matrices of order 4 x 4 in our solution. (excluding initial distance matrix)
  • Diagonal elements of each matrix will always be 0.

 

To learn how to write these matrices step by step, Watch this video.

The four matrices are-

 

The last matrix D4 represents the shortest path distance between every pair of vertices.

 

Get more notes and other study material of Design and Analysis of Algorithms (DAA).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Shortest Path Algorithms | Shortest Path Problems

Shortest Path Problem-

 

  • In general, Shortest path problem is a problem of finding the shortest path(s) between vertices or nodes in the given graph.
  • Shortest path between two vertices is a path that has the least cost as compared to all other paths that exists in the graph.

 

Shortest Path Algorithms-

 

  • Shortest path algorithms are a family of algorithms used for solving shortest path problem.
  • Shortest path algorithms have a wide range of applications such as in-

 

  1. Google Maps
  2. Road Networks
  3. Logistics Research

 

Types of Shortest Path Problem-

 

There are different types of shortest path problem-

 

  1. Single-pair shortest path problem
  2. Single-source shortest path problem
  3. Single-destination shortest path problem
  4. All pairs shortest path problem

 

 

1. Single-pair shortest path problem-

 

  • Single-pair shortest path problem is a shortest path problem in which we find out the shortest path between a pair of vertices of the given graph.
  • A* Search Algorithm is a famous algorithm used for solving single-pair shortest path problem.

 

2. Single-source shortest path problem-

 

  • Single-source shortest path problem is a shortest path problem in which we find out the shortest paths from a given source vertex to all the other remaining vertices of the given graph.
  • Dijkstra’s Algorithm and Bellman Ford Algorithm are the famous algorithms used for solving single-source shortest path problem.

 

3. Single-destination shortest path problem-

 

  • Single-destination shortest path problem is a shortest path problem in which we find out the shortest paths from all the vertices to a single destination vertex of the given graph.
  • By reversing the direction of each edge in the graph, this problem is reduced to a single-source shortest path problem.
  • Dijkstra’s Algorithm is a famous algorithm adapted for solving single-destination shortest path problem.

 

4. All pairs shortest path problem-

 

  • All pairs shortest path problem is a shortest path problem in which we find out the shortest paths between every pair of vertices of the given graph.
  • Floyd-Warshall Algorithm and Johnson’s Algorithm are the famous algorithms used for solving All pairs shortest path problem.

 

Get more notes and other study material of Design and Analysis of Algorithms (DAA).

Watch video lectures by visiting our YouTube channel LearnVidFun.