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:

1.

Need to create a set that keeps track of vertices

included in shortest path tree. Initiallay the set is empty.

2.

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.

3.

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.

ii) Then

include that vertex into the set.

ii) Update

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.

2.2.1 Pseudocode

Algorithm 2.1 Pseudo code for

Dijkstra’s Algorithm

1: Create vertex set Q.

2: for each vertex v in

Graph do

3: distancev

??;

4: predecessorv

?

null;

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

from Q

11: for each neighbor v of u: do

12: alt

?

distanceu + length(u,v)

13: if alt