A general algorithm to implement Dijkstra’s solution for single source shorest path problem


*********************************************************

Input :
Adjacency list representation of graph – a [ ][ ]
A source vertex – s
Output :
distance array – d [ ]

(An array named parent array is used to store the parent node for each node in the final tree structure derived which consists of shotests paths.)

***********************************************************

ALGORITHM:

1) Initialize d[i]=a[s][i] , 1 ≤ i ≤ n.
Set p[i]=s for all i adjacent from s. Set p[i] = 0 for all other vertices.
Create a list L of all vertices for which p[i] ≠ 0.

2)While L is not empty repeate through steps 3 and 4

3)Delete from L the vertex i with least value of d (ties are broken arbritrarily).

4) Up date d[j] to minimum of { d[j] , d[i]+a[i][j] } for all unreached vertices j adjacent from i. If d[j] changes , set p[j] =i , and add j to L in case it is not already there.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s