Dijkstra's algorithm, Data Structure & Algorithms

Assignment Help:

Q. Explain Dijkstra's algorithm for finding the shortest path in the graph given to us.

 Ans:

The Dijkstra's algorithm: This is a problem which is concerned with finding the least cost path from an originating node in a weighted graph to a destination node in that particular graph.

The Dijkstra's algorithm is stated below:

Let G=(V,E) be the simple graph. Let a and z be any two vertices on the graph. Let L(x ) denotes the label of the vertex x which represent the length of shortest path from the vertex a to the vertex x and wij which denotes the weight of the edge eij=

1.  Let P=φ where  P is the set of those vertices which

Are having permanent labels and T={all vertices in graph}

 

Set L(a)=0,

L(x)=∞ for all x≠a

 

2.

Select the

label. This

vertex v in T which has

label is called permanent

the smallest

label of v.

Also set P=P {v} and T=T-{v}

If v=z then L(z) is the length of the shortest path from the vertex a to z and stop.

3.  If  v is  not equal to z    then   revise      the   labels    of vertices of T that is the vertices which do not consist of permanent labels.

The new label of vertex x in T can be given by

L(x)=min(old L(x), L(v)+w(v, x))

Here w(v, x) is the weight of the edge joining the vertex v and x. If there exists no direct edge joining v and x then take w(v, x)= ∞

4.  Repeat steps 2 and 3 until get the permanent z label.


Related Discussions:- Dijkstra's algorithm

Algorithm to add an element at the end of linked list, Write an algorithm t...

Write an algorithm to add an element at the end of circular linked list.   Algorithm to Add the Element at the End of Circular Linked List. IINSENDCLL( INFO, LINK, START, A

Create accessors for this data structure, Create a Money data structure tha...

Create a Money data structure that is made up of amount and currency. (a) Write a constructor for this data structure (b) Create accessors for this data structure (c) Writ

Define binary tree, Define Binary Tree  A binary tree T is explained as...

Define Binary Tree  A binary tree T is explained as a finite set of nodes that is either empty or having of root and two disjoint binary trees TL, and TR known as, respectively

Discuss the brute force algorithm, Question 1 What do you mean by Amortiza...

Question 1 What do you mean by Amortization? Question 2 Explain the following Big Oh notation (O) Omega notation (Ω) Theta notation (Θ)   Question 3 Di

Which sorting methods sorting a list which is almost sorted, Which sorting ...

Which sorting methods would be most suitable for sorting a list which is almost sorted  Bubble Sorting method.

Define about the structure - container, Define about the Structure - Contai...

Define about the Structure - Container - Some containers hold elements in some sort of structure, and some don't. Containers with no structure include bags and sets. Containe

Whether a binary tree is a binary search tree or not, Write an algorithm to...

Write an algorithm to test whether a Binary Tree is a Binary Search Tree. The algorithm to test whether a Binary tree is as Binary Search tree is as follows: bstree(*tree) {

Four applications or implementation of the stack, Q. Write down any four ap...

Q. Write down any four applications or implementation of the stack.                                     Ans. (i)       The Conversion of infix to postfix form (ii)

Comparisons between linear and binary search, Comparative Study of Linear a...

Comparative Study of Linear and Binary Search Binary search is lots quicker than linear search. Some comparisons are following: NUMBER OF ARRAY ELEMENTS EXAMINED array

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