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
Example: Assume the following of code: x = 4y + 3 z = z + 1 p = 1 As we have been seen, x, y, z and p are all scalar variables & the running time is constant irrespective

INSERT FUNCTION /*prototypes of insert & find functions */ list * insert_list(list *); list * find(list *, int); /*definition of  anyinsert function */ list * inser

Search engines employ software robots to survey the Web & build their databases. Web documents retrieved & indexed through keywords. While you enter a query at search engine websit

An undirected graph G with n vertices and e edges is shown by adjacency list.  What is the time required to generate all the connected components? O (e+n)

Part1: Deque and Bag Implementation First, complete the Linked List Implementation of the Deque (as in Worksheet 19) and Bag ADTs (Worksheet 22). Files Needed: linkedList.c Linke

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

Worst Fit method:- In this method the system always allocate a portion of the largest free block in memory. The philosophy behind this method is that by using small number of a ve

Determine in brief the Painter Algorithm a) The farthest polygon, namely the rectangle PQRS, is stored first. (b) The next farthest, the quadrilateral ABCD, is superpo

Abstract Data Types :- A useful tool for specifying the logical properties of a data type is the abstract data type or ADT. The term "abstract data type" refers to the basic mathem

Colouring The use of colours in CAD/CAM has two main objectives : facilitate creating geometry and display images. Colours can be used in geometric construction. In this case,