find shortest path from a to z using dijkstra''s algorithm., Data Structure & Algorithms

Q. In the given figure find the shortest path from A to Z using Dijkstra's Algorithm. 

2234_Dijkstra algorithm.png

 

Ans:

1.  P=φ;  T={A,B,C,D,E,F,G,H,I,J,K,L,M,Z}

Let L(A)=0 and L(x)=∞ for all x in T ( L(x) denotes label of x)

2.  P={A}, T={B,C,D,E,F,G,H,I,J,K,L,M,Z} A≠Z so calculate the new labels for vertices in T

 

L(B)=min(∞, 0+2)=2

L(H)=min(∞, 0+2)=2

L(C)=min(∞, 0+∞)=∞

L(I)=∞

L(D)=∞

L(J)=∞

L(E)=min(∞, 0+2)=2

L(K)=min(∞, 0+2)=2

L(F)=∞

L(L)=∞

L(G)=∞

L(M)= ∞ ; L(Z)= ∞

 

3.  v=B, is the vertex with the smallest label, L(v)=2

P={A,B}, T={C,D,E,F,G,H,I,J,K,L,M,Z} B≠Z so calculate the new labels for vertices in T

 

L(C)=min(∞, 2+4)=6

L(I)=min(∞, 2+2)=4

L(D)=∞

L(J)=∞

L(E)=min(2,2+∞)=2

L(K)=min(2,2+∞)=2

L(F)=∞

L(L)=∞

L(G)=∞

L(M)=∞

L(H)=min(2,2+1)=2

L(Z)= ∞

 

4.  v=E, vertex containing the smallest label, L(v)=2

 

 

P={A,B,E}, T={C,D,F,G,H,I,J,K,L,M,Z} B≠Z so calculate  the new labels for vertices in T

L(C)=min(6, 2+∞)=6

L(J)= ∞

L(D)=∞

L(K)=min(2,2+2)=2

L(F)=min(∞,2+3)=5

 

L(G)=∞

L(L)=∞

L(H)=∞

L(M)=∞

L(I)= ∞

L(Z)= ∞

 

 

5.  v=K, vertex containing the smallest label, L(v)=2

P={A,B,E,K}, T={C,D,F,G,H,I,J,L,M,Z} K≠Z so calculate the new labels for vertices in T

L(C)=min(6, 2+∞)=6

L(J)= ∞

L(D)=∞

L(L)=min(∞,2+4)=6

L(F)=min(5,2+2)=4

L(M)=∞

L(G)=∞

L(Z)= ∞

L(H)=min(∞,2+2)=4

 

L(I)= min(∞,2+3)=5

 

 

6.  v=F, vertex containing the smallest label, L(v)=4

P={A,B,E,K,F}, T={C,D,G,H,I,J,L,M,Z} K≠Z so calculate the new labels for vertices in T

L(C)=min(6, 4+∞)=6

L(I)= min(5,4+∞)=5

L(D)=∞

L(L)=min(6,4+1)=5

L(G)=min(∞,4+4)=8

L(M)=min(∞,4+3)=7

L(G)=∞

L(Z)= ∞

L(H)=min(4,4+∞)=4

L(J)= ∞

 

7.  v=H, vertex containing the smallest label, L(v)=4

P={A,B,E,K,F,H}, T={C,D,G,I,J,L,M,Z}

 

K≠Z so calculate the new labels for vertices in T

L(C)=min(6, 4+∞)=6

L(J)= min(∞,4+∞)=∞

L(D)=∞

L(L)=min(5,4+∞)=5

L(G)=min(8,4+∞)=8

L(M)=min(7,4+∞)=7

L(I)=min(5,4+4)=5

L(Z)= ∞

 

8.  v=I, vertex containing the smallest label, L(v)=5

P={A,B,E,K,F,H,I}, T={C,D,G,J,L,M,Z} I≠Z so calculate the new labels for vertices in T

L(C)=min(6, 5+2)=6

L(L)= min(5,5+1)=5

L(D)=∞

L(M)=min(7,5+∞)=7

L(G)=min(8,5+∞)=8

L(Z)=∞

L(J)=min(∞,5+5)=10

 

 

9.  v=L, vertex containing the smallest label, L(v)=5

P={A,B,E,K,F,H,I,L}, T={C,D,G,J,M,Z}

L≠Z so calculate the new labels for vertices in T

L(C)=min(6, 5+∞)=6

L(J)= min(10,5+2)=7

L(D)=∞

L(M)=min(7,5+3)=7

L(G)=min(8,5+∞)=8

L(Z)=∞

 

10. v=C, vertex containing the smallest label, L(v)=6

P={A,B,E,K,F,H,I,L,C}, T={D,G,J,M,Z} C≠Z so calculate the new labels for vertices in T

L(D)=min(∞,6+3)=9

L(M)= min(7,6+∞)=7

L(G)=min(8,6+∞)=8

L(Z)=∞

L(J)=min(7,6+4)=7

 

 

11. v=J, vertex containing the  smallest label, L(v)=7

P={A,B,E,K,F,H,I,L,C,J}, T={D,G,M,Z} J≠Z so calculate the new labels for vertices in T

L(D)=min(9,7+2)=9

L(M)= min(7,7+2)=7

L(G)=min(8,7+∞)=8

L(Z)=min(∞,7+1)=8

 

12. v=M, vertex containing the smallest label, L(v)=7

P={A,B,E,K,F,H,I,L,C,J,M}, T={D,G,Z} M≠Z so calculate the new labels for vertices in T

L(D)=min(9,7+∞)=9

L(Z)= min(8,7+3)=8

L(G)=min(8,7+1)=8

 

13. v=G, vertex containing the smallest label, L(v)=8

P={A,B,E,K,F,H,I,L,C,J,M,G}, T={D,Z}

G≠Z so calculate the new labels for vertices in T L(D)=min(9,8+∞)=9                                                                          L(Z)= min(8,8+1)=8

 

14. v=z, so now  we stop here,  the Shortest distance is 8

Backtracking all the steps we get, shortest path as: A-K-F-L-J-Z

Posted Date: 7/10/2012 6:53:36 AM | Location : United States







Related Discussions:- find shortest path from a to z using dijkstra''s algorithm., Assignment Help, Ask Question on find shortest path from a to z using dijkstra''s algorithm., Get Answer, Expert's Help, find shortest path from a to z using dijkstra''s algorithm. Discussions

Write discussion on find shortest path from a to z using dijkstra''s algorithm.
Your posts are moderated
Related Questions
One of the best known methods for external sorting on tapes is the polyphase sort. Principle: The basic strategy of this sort is to distribute ordered initial runs of predetermi

Explain the theory of computational complexity A  problem's  intractability  remains  the  similar  for  all  principal  models  of   computations    and   all reasonable inpu

Preconditions assertion A precondition is an assertion which should be true at the initiation of an operation. For instance, a square root operation can't accept a negative a

Complexity classes All decision problems fall in sets of comparable complexity, called as complexity classes. The complexity class P is the set of decision problems which ca

Ruby implements Range of T Abstract data type Ruby implements Range of T ADT in its Range class. Elements of carrier set are represented in Range instances by recording interna

Complexity is the rate at which the needed storage or consumed time rise as a function of the problem size. The absolute growth based on the machine utilized to execute the program

In the present scenario of global warming, the computer hard ware and software are also contributing for the increase in the temperature in the environment and contributing for the

B-trees are special m-ary balanced trees utilized in databases since their structure allows records to be added, deleted & retrieved with guaranteed worst case performance. A B-

Implement algorithm to solve 5-1 fifth order equation given.

Instructions Design and test a reference array. Reference array stores the references to user supplied objects of different types. Just think it as a heterogeneous array wh