The shortest path algorithm is used mainly for
calculating the shortest path of a graph or network. The shortest path problem
is the problem of finding a path between two nodes in a graph or network such
that sum of the weights of its constituent edges is minimized. The algorithms which are used to find the
shortest path are shortest path algorithms 2. In this paper we have discussed
this algorithm only for single source.
2.2 Dijkstra’s Algorithm
Dijkstra’s algorithm1 is one of the
fastest algorithm to track the shortest path from any graph. It is almost
similar to Prim’s algorithm for minimum spanning tree. In Prim’s algorithm we
generate a shortest path tree with the given source. We maintain two sets where
one set is for vertices included in that tree and the other set contains
vertices not yet included in that shortest path tree. At each iteration of the
algorithm, we find a vertex which is in the other set and has minimum distance
from the source.
Steps to measure
the shortest for a single source vertex to all other vertices is given below:
Need to create a set that keeps track of vertices
included in shortest path tree. Initiallay the set is empty.
Need to assign distance value to all vertices in
the input graph. All the distance value must be initialized as INFINITE. Must
assign distance value as 0 for the source vertex so that it is picked first.
While the set (which is mentioned in 1) does not
includes all the vertices
i) Need to pick
a vertex which is not there in the set and has minimum distance value.
include that vertex into the set.
distance value of all adjacent vertices of that vertex. To update the distance
values, iterate through all adjacent vertices. For any adjacent vertex, if the
sum of the distance value for that vertex and weight of edge from vertex to
adjacent vertex is less than the distance value of the adjacent vertex
then update the distance value of adjacent vertex.
Algorithm 2.1 Pseudo code for
1: Create vertex set Q.
2: for each vertex v in
5: add v to Q
6: end for
7: distancesource ? 0
8: while Q is not empty, do
9: u ?
vertex in Q with min distanceu
10: remove u
11: for each neighbor v of u: do
distanceu + length(u,v)
13: if alt