Shortest Path Algorithm

Graphs->Shortest Path Algorithm

Well, you can make out that it concerns to weighted graphs only. After you apply this algorithm you get a TREE, which shows you the shortest paths to all the other vertices from any given starting vertex. Sorry, I am running short of words. I better take an example for this. Consider the weighted graph below.

	Set A as the starting vertex. So, the BFS becomes - A->B->D->C->E->F (Don't ask me why?...find out).
Shortest path from B to A is (BA) = 2
Shortest path from D to A is (DA) = 1
Shortest path from C to A is (CBA) = 3
Shortest path from E to A is (EDA) = 4
Shortest path from F to A is (FCBA) = 5
	You can see there are no alternative paths and no loops in the resultant Shortest Path tree. The tree gives you the shortest path from A to rest of the vertices.

The algorithm is very comprehensive and here it is....

Algorithm:-
Step-1: Set the starting vertex
Step-2: Find the BFS (or DFS) for it
Step-3: For every vertex in the BFS
           A. Find the shortest path from it to the starting vertex
           B. Add that shortest path to the resultant TREE if its already not there and not
               forming a loop

C implementation:-
The implementation in C will be given later on..

Note:- The algorithm has been slightly modified wherein I have asked to find the BFS or DFS. As such you can also proceed without that. I would suggest you to go for BFS if your starting vertex is at much lower breadth level and to go for DFS if it is at a lower depth level. How to find that? Well, in that case your Adjacency list should hold the depth and breadth information, remember.

Index || Doubts / Clarifications || Related Topics || Web Links