Operation of algorithm, Data Structure & Algorithms

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

1831_Operation of Algorithm.png

 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.

1932_Operation of Algorithm1.png

            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

248_Operation of Algorithm2.png

Step 4:

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

Relax v and adjust its predecessor.

 

651_Operation of Algorithm3.png

 Step 5:           

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

724_Operation of Algorithm3.png

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







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
Related Questions
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

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: 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 An entity which holds finitely many other entities. Just as containers such as boxes, baskets, bags, pails, cans, drawers, and so for

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

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.

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

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

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

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