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

Queues, what is the difference between data type and abstract data type

what is the difference between data type and abstract data type

Insert function, INSERT FUNCTION /*prototypes of insert & find function...

INSERT FUNCTION /*prototypes of insert & find functions */ list * insert_list(list *); list * find(list *, int); /*definition of  anyinsert function */ list * inser

Flow chart, that will determine the volume of the sphere or the volume of c...

that will determine the volume of the sphere or the volume of cone or volume of pyramid depending on the choice of the user

Example of single node with multiple elements, The class Element represents...

The class Element represents a single node that can be part of multiple elements on a hotplate and runs in its own thread. The constructor accepts the initial temperature and a hea

Doubly linked list having n nodes, The time required to delete a node x fro...

The time required to delete a node x from a doubly linked list having n nodes is O (1)

Heights of 500 students `Algorithms`, Write an algorithm, using a flowchart...

Write an algorithm, using a flowchart, which inputs the heights of all 500 students and outputs the height of the tallest person and the shortest p erson in the school.

Techniques of representing polynomials using arrays, Q. Explain any three m...

Q. Explain any three methods or techniques of representing polynomials using arrays. Write which method is most efficient or effective for representing the following polynomials.

Define rule-based expert system, 1. Define the following terms in a rule-ba...

1. Define the following terms in a rule-based expert system? a) Knowledge base b) Inference engine 2. What is a fuzzy rule? Explain the difference between classical and fuzzy

Several operations on a aa-tree, The following are several operations on a ...

The following are several operations on a AA-tree: 1. Searching: Searching is done using an algorithm which is similar to the search algorithm of a binary search tree. 2. Ins

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