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

The space - time trade off, The best algorithm to solve a given problem is ...

The best algorithm to solve a given problem is one that requires less space in memory and takes less time to complete its execution. But in practice it is not always possible to

Recursion, i need help in java recursion assignment.

i need help in java recursion assignment.

What are the example of area subdivision method, Example of Area Subdivisio...

Example of Area Subdivision Method The procedure will be explained with respect to an illustrative problem, with the image consisting of five objects, namely a triangle (T), qu

How to measure the algorithm efficiency, How to measure the algorithm's eff...

How to measure the algorithm's efficiency? It is logical to examine the algorithm's efficiency as a function of some parameter n showing the algorithm's input size. Instance

Define an array, Define an array. Array is made up of same data structu...

Define an array. Array is made up of same data structure that exists in any language. Array is set of same data types. Array is the collection of same elements. These same elem

Array, how to define the size of array

how to define the size of array

The smallest element of an array''s index, The smallest element of an array...

The smallest element of an array's index is called its Lower bound.

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