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

Binary tree and binarytree parts, Q. What do you understand by the term Bin...

Q. What do you understand by the term Binary Tree? What is the maximum number of nodes which are possible in a Binary Tree of depth d. Explain the terms given below with respect to

Define the internal path length, Define the Internal Path Length The In...

Define the Internal Path Length The Internal Path Length I of an extended binary tree is explained as the sum of the lengths of the paths taken over all internal nodes- from th

Present the algorithm of binary search. , B i n a ry Search Alg...

B i n a ry Search Algorithm is given as follows 1. if (low > high) 2.     return (-1) 3. mid = (low +high)/2; 4. if ( X = = a [mid]) 5.      return (mid); 6.

Define minimum spanning tree, Define Minimum Spanning Tree A minimum sp...

Define Minimum Spanning Tree A minimum spanning tree of a weighted linked graph is its spanning tree of the smallest weight, where the weight of a tree is explained as the sum

Insertion of a node into an avl tree, Initially Nodes are inserted in an AV...

Initially Nodes are inserted in an AVL tree in the same manner as an ordinary binary search tree. Though, the insertion algorithm for any AVL tree travels back along with the pa

Lists, In the earlier unit, we have discussed about the arrays. Arrays are ...

In the earlier unit, we have discussed about the arrays. Arrays are data structures of fixed size. Insertion & deletion involves reshuffling of array elements. Thus, arraymanipulat

Write down the procedure to reverse a singly linked list. , Ans: A pr...

Ans: A procedure to reverse the singly linked list: reverse(struct node **st) { struct node *p, *q, *r; p = *st; q = NULL; while(p != NULL) { r =q;

Define the external path length, Define the External Path Length The Ex...

Define the External Path Length The External Path Length E of an extended binary tree is explained as the sum of the lengths of the paths - taken over all external nodes- from

Conversion of forest into tree, Conversion of Forest into Tree A binary...

Conversion of Forest into Tree A binary tree may be used to show an entire forest, since the next pointer in the root of a tree can be used to point to the next tree of the for

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