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

Tree, application of threaded binary treee

application of threaded binary treee

Compound interest, Write the algorithm for compound interest

Write the algorithm for compound interest

Storing street addresses with doubly linked lists, Write a C++ program with...

Write a C++ program with header and source les to store street addresses using the Doubly Linked List ADT. Modify the Node class from Lab Assignment 3 so that it becomes a node in

Process of decision making under uncertainty, (a) Describe the steps involv...

(a) Describe the steps involved in the process of decision making under uncertainty. (b) Explain the following principles of decision making: (i) Laplace, (ii) Hurwicz. (c

Program, What is a first-in-first-out data structure ? Write algorithms to...

What is a first-in-first-out data structure ? Write algorithms to perform the following operations on it – create, insertion, deletion, for testing overflow and empty conditions.

Algorithams example, any simple algoritham questions with answers

any simple algoritham questions with answers

What is efficiency of algorithm, What is Efficiency of algorithm? Effic...

What is Efficiency of algorithm? Efficiency of an algorithm can be precisely explained and investigated with mathematical rigor.  There are two types of algorithm efficiency

State a algorithm that inputs the heights of all 500 student, As part of an...

As part of an experiment, a school measured heights (in metres) of all its 500 students. Write an algorithm, using a flowchart that inputs the heights of all 500 students and ou

Double linked list, In a doubly linked list, also called as 2 way list, eac...

In a doubly linked list, also called as 2 way list, each node is divided into 3 parts. The first part is called previous pointer field. It contains the address of the preceding

If, 1. Start 2. Get h 3. If h T=288.15+(h*-0.0065) 4. else if h T=2...

1. Start 2. Get h 3. If h T=288.15+(h*-0.0065) 4. else if h T=216.65 5. else if h T=216.65+(h*0.001) 6. else if h T=228.65+(h*0.0028) 7. else if h T=270.65 8.

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