Operation of algorithm, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Operation of algorithm

Define algorithm, What is an Algorithm? An algorithm is a sequence of u...

What is an Algorithm? An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for getting a needed output for any legitimate input in a finite amoun

Algorithm, Algorithm to find sum of square of a number

Algorithm to find sum of square of a number

Write about enterprise manager, Question 1 . Give the structure of PL/SQL B...

Question 1 . Give the structure of PL/SQL Blocks and explain Question 2 . Differentiate between PL/SQL functions and procedures Question 3 . Explain the following Par

Collision resolution techniques, complete information about collision resol...

complete information about collision resolution techniques

Algorithm to find maximum and minimum numbers, Give an algorithm to find bo...

Give an algorithm to find both the maximum and minimum of 380 distinct numbers that uses at most 568 comparisons.

Deletion of a node from a binary search tree, The algorithm to delete any n...

The algorithm to delete any node having key from a binary search tree is not simple where as several cases has to be considered. If the node to be deleted contains no sons,

#, write an algorithm to search a particular node in linked list which retu...

write an algorithm to search a particular node in linked list which returns " FOUND" or "NOT FOUND" as outcome.

Queue, algorithm for insertion in a queue using pointers

algorithm for insertion in a queue using pointers

State about the pseudocode, State the Introduction to pseudocode No spe...

State the Introduction to pseudocode No specific programming language is referred to; development of algorithms by using pseudocode uses generic descriptions of branching, loop

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd