Data Structures Using C, 2nd Edition by Pearson

406 Data Structures Using C

for ( j = 2; j <= N; j++)

{

if (visited [j] = 0 && dist[j] < min )

{

pos = j;

min = dist[j];

}

}

/* Add the vertex (i.e. pos)

visited [pos] = 1; S[i] = pos;

/* for each vertex adjacent to pos, update distances */

for ( k = 2; k <=N; k++)

{

if (visited [k] == 0)

if ( dist (pos) + cost [pos][k] < dist [k])

dist [k] = dist (pos) + cost [pos][k];

}

}

Consider the graph given in Figure 8.39.

The corresponding cost matrix and the stepwise

construction of shortest cost of all vertices with re-

spect to vertex V1 is given in Figure 8.40.

V1

V3

V5

V4

V2

2

3

2

1

6

2

4

5

Fig. ...