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
Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

What is a linear array? An array is a way to reference a series of memory locations using the similar name. Every memory location is shown by an array element. An  array elemen

Q. Write an algorithm that counts number of nodes in a linked list.                                       A n s . Algo rithm to Count No. of Nodes in Linked List C

#quCreate a flowchart to show the process that will allow the implementation of Queue, Enqueue, and Dequeue operations.estion..

Q. Define a method for keeping two stacks within a single linear array S in such a way that neither stack overflows until entire array is used and a whole stack is never shifted to

Warnock's Algorithm An interesting approach to the hidden-surface problem was presented by Warnock. His method does not try to decide exactly what is happening in the scene but

two standards ways of traversing a graph in data structure

adjacency multilist

What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

#why all the 4 operations i.e. insertion n deletion from rear end and front end is valid in input restricted DEQUE