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

Data Structure, Ask consider the file name cars.text each line in the file ...

Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

Algorithm, Ask question #MWhich of the following is not a characteristic of...

Ask question #MWhich of the following is not a characteristic of good algorithm? inimum 100 words accepted#

Algorithm of binary search, Step 1: Declare array 'k' of size 'n' i.e. k(n)...

Step 1: Declare array 'k' of size 'n' i.e. k(n) is an array which stores all the keys of a file containing 'n' records Step 2: i←0 Step 3: low←0, high←n-1 Step 4: while (l

Deletion, sir how can i explain deletion process in a data structure

sir how can i explain deletion process in a data structure

Which sorting algorithm is adaptable to singly linked list, Which sorting a...

Which sorting algorithm is easily adaptable to singly linked lists? Simple Insertion sor t is easily adabtable to singly linked list.

Data communication, #question.explain different types of errors in data tra...

#question.explain different types of errors in data transmission.

Algorithms, write short note on algorithms

write short note on algorithms

Algorithms and flowcharts, write an algorithm and draw a flowchart to calcu...

write an algorithm and draw a flowchart to calculate the perimeter and area of a circle

Define chaining process of hashing, Chaining In this method, instead of...

Chaining In this method, instead of hashing function value as location we use it as an index into an array of pointers. Every pointer access a chain that holds the element havi

Pre-order and post order traversal of a binary tree, The pre-order and post...

The pre-order and post order traversal of a Binary Tree generates the same output. The tree can have maximum One node

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