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

Siso-4bit register, explain working of siso-register to store 1011 and show...

explain working of siso-register to store 1011 and show timing diagram &table

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,

Tradeoff between space and time complexity, We might sometimes seek a trade...

We might sometimes seek a tradeoff among space & time complexity. For instance, we may have to select a data structure which requires a lot of storage to reduce the computation tim

Sorting, Define Hashing. Store the following values in a hash table of tabl...

Define Hashing. Store the following values in a hash table of table size 11 using division method: 25, 42, 96, 101, 102, 162, and 197. In case of collision, use other hash functio

Define different types of sparse matrix, Q1. Define a sparse matrix. Explai...

Q1. Define a sparse matrix. Explain different types of sparse matrices? Evaluate the method to calculate address of any element a jk of a matrix stored in memory. Q2. A linear

Threaded binary tree, i need the full concept of it... please can anyone pr...

i need the full concept of it... please can anyone provide

Implement an open hash table, In a chained hash table, each table entry is ...

In a chained hash table, each table entry is a pointer to a collection of elements. It can be any collection that supports insert, remove, and find, but is commonly a linked list.

Define the terms - key attribute and value set, Define the terms   ...

Define the terms     i) Key attribute     ii) Value set  Key attribute:  An entity  type  usually  has  an attribute  whose  values  are  distinct  fr

Data Structure, Ask consider the file name cars.text each line in the file ...

Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

Preorder - postorder and inorder, 1) preorder, postorder and inorder 2) ...

1) preorder, postorder and inorder 2) The main feature of a Binary Search Tree is that all of the elements whose values is less than the root reside into the nodes of left subtr

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