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.
Related Operations:
Concept
-- non-directed, directed and weighted
Adjacency matrix of a Graph
Linked representation of a Graph
Traversals
– Depth First & Breadth first Search
Transitive closure/ Warshall’s algorithm
Shortest Path Algorithm
Spanning Tree Algorithm
|
