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
Define the term counting - Pseudocode Counting in 1s is quite simple; use of statement count = count + 1 would enable counting to be done (for example in controlling a repeat

#include #include int sumFact(int numb); int calculateFactorial(int digit); main() { int numb, sumfact; do{ printf ("Enter a number 1 to 9999\n"); scanf("%

Q. The reason bubble sort algorithm is inefficient is that it continues execution even after an array is sorted by performing unnecessary comparisons. Therefore, the number of comp

What are circular queues?  Circular queue: Static queues have a very large drawback that once the queue is FULL, even though we erase few elements from the "front" and relieve

Illustrates the program segment for Quick sort. It uses recursion. Program 1: Quick Sort Quicksort(A,m,n) int A[ ],m,n { int i, j, k; if m { i=m; j=n+1; k

For the following graph find the adjacency matrix and adjacency list representation of the graph.

Explain the Scan-Line Algorithm This image-space method for removing hidden surfaces is an extension of the scan-line algorithm for filling polygon interiors. Instead of fillin

Typical programming languages such as Pascal, C or Java give primitive data kinds such as integers, boolean, reals values and strings. They give these to be organised into arrays,

Optimal solution to the problem given below. Obtain the initial solution by VAM Ware houses Stores Availibility I II III IV A 5 1 3 3 34 B 3 3 5 4 15 C 6 4 4 3 12 D 4 –1 4 2 19 Re

Q. A Binary tree comprises 9 nodes. The preorder and inorder traversals of the tree yield the given sequence of nodes: Inorder :          E     A    C    K    F     H    D