Shortest Path Algorithm

(Shortest Path Algorithm) A directed graph  G with M nodes is maintained in memory by its weight matrix W. This algorithm finds a matrix Q such that Q[I,J] is the length of a shortest path from node VI tonode VJ.Infinity is a very large number, and MIN is the minimum value function.

1.  Repeat for I, J = 1, 2......, M: [Initializes P].

      W[I, J] = 0, then : Set Q[I, J]:=INFINITY;

 Else: Set Q[I, J] : = W[I, J].

[End of loop.]

2.  Repeat Steps 3 and 4 for K = 1, 2, ......., : [Updates P.]

3.  Repeat Step 4 for I = 1, 2,....,M:

4.                Repeat for J = 1, 2,......,M:

                                       Set Q[I, J] : = MIN(Q[I, J],  Q[I, K]  + Q[K, J]).

[End of loop].

[End of Step 3 loop]

[End of Step 2 loop]

5.Exit.

If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVE