Dijkstras algorithm, Data Structure & Algorithms

Assignment Help:

Djikstra's algorithm (named after it is discovered by Dutch computer scientist E.W. Dijkstra) resolves the problem of finding the shortest path through a point in a graph (the source) to a destination along non-negative weight edge.

It turns out that one can determine the shortest paths from given source to all vertices (points) into a graph in the similar time. Therefore, this problem is sometimes called the single-source shortest paths problem. Dijkstra's algorithm is greedy algorithm, which determine shortest path among all pairs of vertices within the graph. Before defining the algorithms formally, let us study the method through an example.

1564_Dijkstras Algorithm.png

Figure: A Directed Graph with no negative edge(s)

Dijkstra's algorithm has two sets of vertices that are following:

S   = set of vertices whose shortest paths from the source have been determined already

Q = V-S is the set of remaining vertices.

The other data structures required are following:

d is array of best estimates of shortest path to each of the  vertex from the source

pi is array of predecessors for each of vertex. predecessor is an array of vertices to which shortest path has already been find out.

The fundamental operation of Dijkstra's algorithm is edge relaxation. If there is any edge from u to v, then the shortest known path from s to u can be extended to a path from s to v by adding up edge (u,v) at the end. This path will have length d[u]+w(u,v). If this is less than d[v], we can replace the current value of d[v] along with new value.

The predecessor list is an array of indices, one for each vertex of any graph. Each vertex entry has the index of its predecessor in a path through the graph.


Related Discussions:- Dijkstras algorithm

Use of asymptotic notation in the study of algorithm, Q. What is the need o...

Q. What is the need of using asymptotic notation in the study of algorithm? Describe the commonly used asymptotic notations and also give their significance.

Simplifying assumptions of wire frame representation, Simplifying Assumptio...

Simplifying Assumptions of wire frame representation Neglect colour - consider Intensity: For now we shall forget about colour and restrict our discussion just to the intensi

Illumination of wire frame, Illumination of wire frame The colour or sh...

Illumination of wire frame The colour or shade that a surface appears to the human eye depends primarily on three  factors : Colour and strength of incoming illumination

The number of different directed trees with 3 nodes, The number of differen...

The number of different directed trees with 3 nodes are ?? The number of disimilar directed trees with three nodes are 3

Bubble sort, Q. The reason bubble sort algorithm is inefficient is that it ...

Q. The reason bubble sort algorithm is inefficient is that it continues execution even after an array is sorted by performing unnecessary comparisons. Therefore, the number of comp

Red-black trees, A Red-Black Tree (RBT) is a type of Binary Search tree wit...

A Red-Black Tree (RBT) is a type of Binary Search tree with one extra bit of storage per node, i.e. its color that can either be red or black. Now the nodes can have any of the col

Program for linear search, Program for Linear Search. Program: Linear S...

Program for Linear Search. Program: Linear Search /*Program for Linear Search*/ /*Header Files*/ #include #include /*Global Variables*/ int search; int

Omega notation, The ?-Notation (Lower Bound) This notation provides a l...

The ?-Notation (Lower Bound) This notation provides a lower bound for a function to within a constant factor. We write f(n) = ?(g(n)), if there are positive constants n 0 and

Deletion of any element from the circular queue, Algorithm for deletion of ...

Algorithm for deletion of any element from the circular queue: Step-1: If queue is empty then say "queue is empty" & quit; else continue Step-2: Delete the "front" element

Binary tree creation, Binary tree creation struct NODE { struct N...

Binary tree creation struct NODE { struct NODE *left; int value; struct NODE *right; }; create_tree( struct NODE *curr, struct NODE *new ) { if(new->val

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