Shortest path dijkstras algorithm, Data Structure & Algorithms

Assignment Help:

* Initialise d & pi*

for each vertex v within V( g )

g.d[v] := infinity

 g.pi[v] := nil

g.d[s] := 0;

* Set S to empty *

S := { 0 }

 Q := V(g)

* While (V-S) is not null*

while not Empty(Q)

1.   Sort the vertices within V-S according to the current best estimate of their distance from the source

 u := Extract-Min ( Q );

2.   Add vertex u, the closest vertex into V-S, to S, Add Node( S, u );

3.   Relax all of the vertices yet in V-S connected to u

relax( Node u, Node v, double w[][] )

if d[v] > d[u] + w[u]v] then

d[v] := d[u] + w[u][v]

pi[v] := u

 

In brief, this algorithm begins by assigning a weight of infinity to all of vertices, and then choosing a source & assigning a weight of zero to it. Vertices are added up to the set for which shortest paths are known. While a vertex is chosen, the weights of its adjacent vertices are relaxed. Once all of vertices are relaxed, their predecessor's vertices are updated (pi). The cycle of selection, weight relaxation & predecessor update is repeated till the shortest path to all vertices has been determined.


Related Discussions:- Shortest path dijkstras algorithm

State about the pseudocode, State the Introduction to pseudocode No spe...

State the Introduction to pseudocode No specific programming language is referred to; development of algorithms by using pseudocode uses generic descriptions of branching, loop

Insertion sort, Data array A has data series from 1,000,000 to 1 with step ...

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

Doubly linked list having n nodes, The time required to delete a node x fro...

The time required to delete a node x from a doubly linked list having n nodes is O (1)

Algorithmic implementation of multiple stacks, So far, we now have been con...

So far, we now have been concerned only with the representation of single stack. What happens while a data representation is required for several stacks? Let us consider an array X

What is an algorithm, What is an algorithm?  What are the characteristics o...

What is an algorithm?  What are the characteristics of a good algorithm? An algorithm is "a step-by-step process for accomplishing some task'' An algorithm can be given in many

Techniques of representing polynomials using arrays, Q. Explain any three m...

Q. Explain any three methods or techniques of representing polynomials using arrays. Write which method is most efficient or effective for representing the following polynomials.

Abstract Data Types, A useful tool which is used for specifying the logical...

A useful tool which is used for specifying the logical properties of a data type is called the abstract data type or ADT. The term "abstract data type" refers to the fundamental ma

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