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

Write an algorithm to measure daily temperatures, A geography class decide ...

A geography class decide to measure daily temperatures and hours of sunshine each day over a 12 month period (365 days) Write an algorithm, using a flowchart that inputs tempera

Determine the importance of array, Determine the importance of array Ar...

Determine the importance of array Arrays are significant since they allow many values to be stored in a single data structure whereas providing very fast access to each value.

How to construct binary tree, Q. A Binary tree comprises 9 nodes. The preor...

Q. A Binary tree comprises 9 nodes. The preorder and inorder traversals of the tree yield the given sequence of nodes: Inorder :          E     A    C    K    F     H    D

Sorting on several keys, Thus far, we have been considering sorting depend ...

Thus far, we have been considering sorting depend on single keys. However, in real life applications, we may desire to sort the data on several keys. The simplest instance is that

Define a procedure called make-avl-tree, This question deals with AVL trees...

This question deals with AVL trees. You must use mutable pairs/lists to implement this data structure: (a) Define a procedure called make-avl-tree which makes an AVL tree with o

Calculation of storage complexity, Since memory is becoming more & cheaper,...

Since memory is becoming more & cheaper, the prominence of runtime complexity is enhancing. However, it is very much significant to analyses the amount of memory utilized by a prog

Graphs with negative edge costs, We have discussed that the above Dijkstra'...

We have discussed that the above Dijkstra's single source shortest-path algorithm works for graphs along with non-negative edges (like road networks). Given two scenarios can emerg

Explain open addressing, Open addressing The easiest way to resolve a c...

Open addressing The easiest way to resolve a collision is to start with the hash address and do a sequential search by the table for an empty location.

Which data structure is used for implementing recursion, Which data structu...

Which data structure is used for implementing recursion Stack.

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