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

Division-remainder hashing, According to this, key value is divided by any ...

According to this, key value is divided by any fitting number, generally a prime number, and the division of remainder is utilized as the address for the record. The choice of s

Advantage of list over arrays, The advantage of list over Arrays is flexibi...

The advantage of list over Arrays is flexibility. Over flood is not a problem until the computer memory is bushed. When the individual record are quite large, it may be difficult t

Merge sort , What is the best-case number of comparisons performed by merge...

What is the best-case number of comparisons performed by mergesort on an input sequence of 2 k distinct numbers?

Define graph, A graph is a mathematical structure giving of a set of vertex...

A graph is a mathematical structure giving of a set of vertexes (v1, v2, v3) and a group of edges (e1, e2, e3). An edge is a set of vertexes. The two vertexes are named the edge en

Time complexity, The  total  of  time  needed  by  an algorithm to run to i...

The  total  of  time  needed  by  an algorithm to run to its completion is termed as time complexity. The asymptotic running time of an algorithm is given in terms of functions. Th

The best average behaviour, The best average behaviour is shown by  Qui...

The best average behaviour is shown by  Quick Sort

Program, insertion and deletion in a tree

insertion and deletion in a tree

State warnock algorithm, Warnock's Algorithm An interesting approach to...

Warnock's Algorithm An interesting approach to the hidden-surface problem was presented by Warnock. His method does not try to decide exactly what is happening in the scene but

A bst is traversed in which order recursively, A  BST is traversed in the ...

A  BST is traversed in the following order recursively: Right, root, left e output sequence will be in In Descending order

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