Operation of Algorithm

The following sequence of diagrams shows the operation of Dijkstra's Algorithm. The bold vertices show the vertex to which shortest path has been find out.

Step 1:

Initialize the graph, all of the vertices have infinite costs except the source vertex that has zero cost

 Step 2

From all the adjacent vertices, select the closest vertex to the source s.

As we initialized d[s] through 0, it's s. (illustrated in bold circle)

Add it to S

Relax all vertices adjacent to s, that means u & x

Update vertices u & x by 10 & 5 as the distance from s.

            Step 3:

Select the nearest vertex, x. Relax all of vertices adjacent to x

Update predecessors for u, v & y. Predecessor of x = s

Predecessor of v = x ,s

Predecessor of y = x ,s

add x to S

Step 4:

Now y is the closest vertex. Add it to S.

Relax v and adjust its predecessor.

 

 Step 5:           

u is now closest, add it to S and adjust its adjacent vertex, v.

Step 6:

Finally, add v to S.

The predecessor list now defines the shortest path from each node to s.

Posted Date: 4/11/2013 4:04:47 AM | Location : United States

Ask an Expert

Related Discussions:- Operation of algorithm, Assignment Help, Ask Question on Operation of algorithm, Get Answer, Expert's Help, Operation of algorithm Discussions

Write discussion on Operation of algorithm
Your posts are moderated

Write your message here..

Related Questions

Surrounding of sub division method, Surrounding of sub division method ... Surrounding of sub division method A polygon surrounds a viewport if it completely encloses or covers the viewport. This happens if none of its sides cuts any edge of the viewp

Algorithm for sorting a deck of cards, What is wrong with the following alg... What is wrong with the following algorithm for sorting a deck of cards (considering the basic properties of algorithms)? I. Put the cards together into a pile II. For each ca

Full binary trees, Full Binary Trees: A binary tree of height h that had 2... Full Binary Trees: A binary tree of height h that had 2h -1 elements is called a Full Binary Tree. Complete Binary Trees: A binary tree whereby if the height is d, and all of

Explain in brief about the container, Explain in brief about the Container ... Explain in brief about the Container An entity which holds finitely many other entities. Just as containers such as boxes, baskets, bags, pails, cans, drawers, and so for

Polynomials, Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8... Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8  can  be  represented by using arrays. Arithmetic operations such as addition & multiplication of polynomials are com

STACK, 5. Implement a stack (write pseudo-code for STACK-EMPTY, PUSH, and P... 5. Implement a stack (write pseudo-code for STACK-EMPTY, PUSH, and POP) using a singly linked list L. The operations PUSH and POP should still take O(1) time.

Non-recursive implementation of preorder traversal, For preorder traversal,... For preorder traversal, in the worst case, the stack will rise to size n/2, where n refer to number of nodes in the tree. Another method of traversing binary tree non-recursively t

Shortest path algorithms, A driver takes shortest possible route to attain ... 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

Data structure, Ask question #Minimum 1Mark each of the following statement... Ask question #Minimum 1Mark each of the following statements as valid or invalid. If a statement is invalid, explain why. a. current ¼ list; b. temp->link->link ¼ NULL; c. trail->l

Binary search technique, Q. Describe the basic concept of binary search tec... Q. Describe the basic concept of binary search technique? Is it more efficient than the sequential search?         Ans : The bin ary search technique:- This tec