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

Explain the concept of colouring, Colouring The use of colours in CAD/C... 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,

Algorithm to add an element at the end of linked list, Write an algorithm t... 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, What is Algorithm A finite sequence of steps for 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

Program of implementation of stack using arrays, include int choice, st... include int choice, stack[10], top, element; void menu(); void push(); void pop(); void showelements(); void main() { choice=element=1; top=0; menu()

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

Algorithm for binary search, Q. Write down the algorithm for binary search.... 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, Define data model?  A data model is a collection of ... 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 inputs speed of cars using pseudocode, Write an algorith... 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 floyds algorithm, Explain Floyd's algorithm It is convenient to... 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

Algorithm for pre-order traversal, Hear is given a set of input representin... 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