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

Linked list implementation of any circular queue, Link list representation ...

Link list representation of a circular queue is more efficient as it employs space more competently, of course with the added cost of storing the pointers. Program 7 gives the link

Lilz, I need to know about data structure and algorithms. can you help me?

I need to know about data structure and algorithms. can you help me?

Array implementation of a queue, Since the stack is list of elements, the q...

Since the stack is list of elements, the queue is also a list of elements. The stack & the queue differ just in the position where the elements may be added or deleted. Similar to

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

Array, how to define the size of array

how to define the size of array

Illustrate trivariate colour models, Illustrate Trivariate Colour Models ...

Illustrate Trivariate Colour Models Conventional colour models based on the tristimulus theory all contain three variables and so are called trivariate models. Let us now consi

Program for linear search, Program for Linear Search. Program: Linear S...

Program for Linear Search. Program: Linear Search /*Program for Linear Search*/ /*Header Files*/ #include #include /*Global Variables*/ int search; int

Multidimensional array in one dimensional array, Q. By giving an example sh...

Q. By giving an example show how multidimensional array can be represented in one the dimensional array.

Explain the interfaces in ruby, Explain the Interfaces in Ruby Recall...

Explain the Interfaces in Ruby Recall that in object-oriented programming, an interface is a collection of abstract operations that cannot be instantiated. Even though Ruby i

State the ways to construct container taxonomy, State the ways to construct...

State the ways to construct container taxonomy There are several ways that we could construct our container taxonomy from here; one way that works well is to make a fundamental

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