All pairs shortest paths algorithm, Data Structure & Algorithms

Assignment Help:

In the last section, we discussed regarding shortest path algorithm that starts with a single source and determines shortest path to all vertices in the graph. In this section, we will discuss the problem of finding shortest path among all pairs of vertices in a graph. This problem is helpful in finding distance among all pairs of cities in a road atlas. All pairs shortest paths problem is mother of all of the shortest paths problems.

In this algorithm, we shall represent the graph through adjacency matrix.

The weight of an edge Cij in an adjacency matrix representation of any directed graph is represented as follows

1625_All Pairs Shortest Paths Algorithm.png

Given directed graph G = (V, E), where each edge (v, w) contain a non-negative cost C(v , w), for all of the pairs of vertices (v, w) to determine the lowest cost path from v to w.

The All pairs shortest paths problem can be considered as a generalisation of single- source-shortest-path problem, using Dijkstra's algorithm by varying the source node amongst all the nodes in the graph. If negative edge(s) is allowed, then we can't employ Dijkstra's algorithm.

In this segment we will employ a recursive solution to all pair shortest paths problem known as Floyd-Warshall algorithm, which runs in O(n3) time.

This algorithm is depends on the following principle. For graph G let V = {1, 2,3,...,n}.Let us assume a sub set of the vertices {1, 2, 3, .....,k. For any pair of vertices which belong to V, assume all paths from i to j whose intermediate vertices are from {1, 2, 3, ....k}. This algorithm will exploit the relationship among path p and shortest path from i to j whose intermediate vertices are from {1, 2, 3, ....k-1} with the given two possibilities:

1.   If k is not any intermediate vertex in the path p, then all of the intermediate vertices of the path p are in {1, 2, 3, ....,k-1}. Therefore, shortest path from i to j along intermediate vertices in {1, 2, 3, ....,k-1} is also the shortest path from i to j along vertices in {1, 2, 3, ..., k}.

2.   If k is intermediate vertex of the path p, we break down the path p in path p1 from vertex i to k and path p2 from vertex k to j. So, path p1 is the shortest path from i to k  along with intermediate vertices in {1, 2, 3, ...,k-1}.

Throughout iteration process we determine the shortest path from i to j using only vertices (1, 2,3, ..., k-1} and in the next step, we determine the cost of using the kth vertex as an intermediate step. If this results into lower cost, then we store it.

After n iterations (all possible iterations), we determine the lowest cost path from i to j by using all vertices (if essential).

Notice the following:

Initialize the matrix

 C[i][ j] = ∞ if (i, j) does not associate with E for graph G = (V, E)

 Initially, D[i][j] = C[i][j]

We also term a path matrix P where P[i][j] holds intermediate vertex k on the least cost path from i to j which leads to the shortest path from i to j .


Related Discussions:- All pairs shortest paths algorithm

In-order traversal, Write steps for algorithm for In-order Traversal Th...

Write steps for algorithm for In-order Traversal This process when implemented iteratively also needs a stack and a Boolean to prevent the execution from traversing any portion

Total weight of minimum spanning tree, a) Run your program for α = 0.05, 0...

a) Run your program for α = 0.05, 0.5, and 0.95. You can use n = 30, and W = 10. What is impact of increasing value of α on connectivity of G'? To answer this question, for each v

What are expression trees, What are expression trees?  The leaves of an...

What are expression trees?  The leaves of an expression tree are operands, like as constants or variable names, and the other nodes have operators. This certain tree happens to

Total impedent of the circuit, an electrical student designed a circuit in...

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

What is diffuse illumination, Diffuse Illumination Diffuse illuminatio...

Diffuse Illumination Diffuse illumination means light that comes from all directions not from one particular source. Think about the light of a grey cloudy day as compared to

What is quick sort, What is quick sort? Quick sort is a sorting algorit...

What is quick sort? Quick sort is a sorting algorithm that uses the idea if split and conquer. This algorithm chooses an element called as pivot element; search its position in

Basic concept of the primitive data structures, Q. Explain the basic concep...

Q. Explain the basic concept of the primitive data structures.                                             Ans. The concept of P r i m i t i ve Data

Encryption the plain-text using the round keys, Encryption the plain-text u...

Encryption the plain-text using the round keys: 1. (Key schedule) Implement an algorithm that will take a 128 bit key and generate the round keys for the AES encryption/decryp

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd