Discrete Math Find the shortest path length from v1 to v6 in

Discrete Math

Find the shortest path length from v1 to v6 in the following undirected graph using the shortest- length variant of Algorithm WARSHALL from [26].

Solution

The floyd warshall algorithm will work in steps

Distance from source vertex to itself is 0 and remaining vertex is infinite

Now starting from the source vertex to the nearest neigbhours will update the value

v1-> v2 = 7 and v1->v4 = 2

now v4->v5 = 1 and v1->v5 = min( v1->v4 + v4->v5 ,v1->v2 + v2->v5)= 3

v2->v3 = 9 and v1->v3 = v1->v2 + v2->v3 = 7 + 2 = 9 units

Now in the next iteration

v1->v6 = min(v1->v4->v5->v6,v1->v2->v3->v6) = 13

Similarly we will get the path updated for the path

v1->v3 = 8 then we get the shortest path length from v1 to v6

=> v1->v3 + v3->v6 = 12 units

The shortest path will be from v1->v4->v5->v2->v3->v6

0	Infinite	Infinite	Infinite	Infinite	Infinite
Infinite	Infinite	Infinite	Infinite	Infinite	Infinite
Infinite	Infinite	Infinite	Infinite	Infinite	Infinite
Infinite	Infinite	Infinite	Infinite	Infinite	Infinite
Infinite	Infinite	Infinite	Infinite	Infinite	Infinite
Infinite	Infinite	Infinite	Infinite	Infinite	Infinite