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
what is the impoartance of average case analysis of algorithm

A driver takes shortest possible route to attain destination. The problem which we will discuss here is similar to this type of finding shortest route in any specific graph. The gr

Q. Explain the Hash Tables, Hash function and Hashing Techniques properly?             A n s . H as h Table is explained as follows : A hash table is a data struc

Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

Define about the Structure - Container - Some containers hold elements in some sort of structure, and some don't. Containers with no structure include bags and sets. Containe

Each of the comparison in the binary search decrease the number of possible candidates where the key value can be searched by a factor of 2 as the array is divided into two halves

1. Give both a high-level algorithm and an implementation (\bubble diagram") of a Turing machine for the language in Exercise 3.8 (b) on page 160. Use the ' notation to show the co

Painter's Algorithm As the name suggests, the algorithm follows the standard practice of a painter, who  would paint the background (such as a backdrop) first, then the major d

It is a naturally occurring sorting method exemplified through a card player arranging the cards dealt to him. He picks up the cards like they are dealt & added them into the neede

We have discussed already about three tree traversal methods in the earlier section on general tree. The similar three different ways to do the traversal -inorder , preorder, and p