Floyd Warshall’s Algorithm

The Floyd Warshall’s Algorithm is used to find the shortest path between any two nodes in a given graph. It keeps a matrix of distances between each pair of vertices.it will continue iterating the matrix until it reaches at a shortest path.

Algorithm:

1: Using the data about the graph, make a matrix.

2: By taking all vertices as an intermediate vertex, we have to update the final matrix.

3: It is to be noted that it includes at a time we pick one vertex, and we update the shortest path which includes this chosen vertex as an in-between point along the path.

4: When we select a vertex say k almost like the middle of the path, in previous calculations we have already taken all vertices P{0,1,2..,k-1} as potential middle points.

5: We have to consider the following subpoints while dealing with the source and destination vertices I,j respectively

• If vertex k is not the part of shortest path from I to j, we don’t have to change dist[i][j] value .ie, it will remain unchanged.
• If vertex k is indeed part of shortest path from I to j, update dist[i][j] to the sum of dist[i][k] and dist[k][j] but note that only if dist[i][j] is greater than this value we newly calculated.

Example: Consider the given graph G,

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

Step 6:

Step 7:

In between sending and receiving data packets from the sender to the receiver, it will go through many routers and subnets. So as a part of increasing the efficiency in routing the data packets and decreasing the traffic, we must find the shortest path. In this article, we are discussing the shortest path algorithms.