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
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,

Write an algorithm to add an element at the end of circular linked list.   Algorithm to Add the Element at the End of Circular Linked List. IINSENDCLL( INFO, LINK, START, A

What is Algorithm A finite sequence of steps for accomplishing some computational task. An algorithm should Have steps which are simple and definite enough to be done

include int choice, stack[10], top, element; void menu(); void push(); void pop(); void showelements(); void main() { choice=element=1; top=0; menu()

Define File organization''s and it''s types

Q. Write down the algorithm for binary search. Which are the conditions under which sequential search of a list is preferred over the binary search?

Define data model?  A data model is a collection of conceptual tools for explaning data, data relationships, data semantics and consistency constraints.

Write an algorithm by using pseudocode which: Inputs top speeds of 5000 cars Outputs fastest speed and the slowest speed Outputs average speed of all the 5000 cars

Explain Floyd's algorithm It is convenient to record the lengths of shortest paths in an n by n matrix D known as the  distance matrix: the element d ij   in the i th   row an

Hear is given a set of input representing the nodes of a binary tree, write a non recursive algorithm that must be able to give the output in three traversal orders. Write down an