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

**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.

### Like this:

Like Loading...

*Related*