advantages and disadvantages of dijkstra algorithm ppt
#1

what are the advantage & disadvantage of dijkstra's algorithm
Reply
#2

Dijkstra's algorithm is called the single-source shortest path. It is also known as
the single source shortest path problem. It computes length of the shortest
path from the source to each of the remaining vertices in the graph.
The single source shortest path problem can be described as follows:
Let G= {V, E} be a directed weighted graph with V having the set of vertices.
The special vertex s in V, where s is the source and let for any edge e in E,
EdgeCost(e) be the length of edge e. All the weights in the graph should be
non-negative.
Before going in depth about Dijkstra’s algorithm let’s talk in detail about
directed-weighted graph.
Directed graph can be defined as an ordered pair G: = (V,E) with V is a set,
whose elements are called vertices or nodes and E is a set of ordered pairs of
vertices, called directed edges, arcs, or arrows. Directed graphs are also known
as digraph.

Advantage
Finds shortest path in O( E+ V Log(V) ) if you use a min priority queue.
This is true only if you implement priority queue with Fibonacci heap, then amortized operation over it will take O(1). Otherwise, if you use any other implementation of priority_queue (like standard C++ STL) it should take E log(E) + V. (courtesy Roman Iedemskyi)
Disadvantage
Fails in cases where you have a negative edge
Dijkstra's Algorithm
- If a graph contains a negative weight cycle, then some shortest paths may be found incorrectly.
- O(m.log(n)) running time using heaps. (This implementation is almost identical to prim's alg.)
- Dijkstra's algorithm is a great algorithm. If the graph fits to main memory and all edges are nonnegative and if you use heaps , you will get a very fast and always correct shortest path solutions.
- Two disadvantages: 1- Not worked for negative cycles 2- Highly centralized, not very distributed(relevant for internet routing)

Take an initial vertex S.
Relax all edges leaving the initial vertex S.

Extract minimum -> X
Relax all edges leaving X

Extract minimum -> Y
Relax all edges leaving Y

Extract minimum -> Z
Relax all edges leaving Z

Extract minimum -> Q
Relax all edges leaving Q

Extract minimum -> W
Relax all edges leaving W

Extract minimum -> E
Relax all edges leaving E
.
.
.

- Dijkstra's algorithm is an example of greedy algorithm

- Here is metu resource explaining the topic : http://cow.ceng.metu.edu.tr/Courses/inde...ster=20121
Here is an example : http://youtubewatch?v=8Ls1RqHCOPw
Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page
Popular Searches: advantages of sha 1 algorithm ppt, md5 algorithm advantages and disadvantages, advantages and disadvantages of blowfish algorithm ppt, shortest path dijkstra, simulation of dijkstra s algorithm, advantages and disadvantages of booth s algorithm, advantages and disadvantages of rc2 algorithm,

[-]
Quick Reply
Message
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  well-spring some homemade barbecue backchat and moistureless rubs and the actuality 0 1,025 10-09-2019, 05:48 PM
Last Post:
  agent some homemade barbecue cheek and prosaic rubs and suit 0 942 10-09-2019, 07:04 AM
Last Post:
  pass some homemade barbecue coolness and arid rubs and module 0 898 09-09-2019, 06:35 PM
Last Post:
Wink disadvantages of plastic in malayalam essay 2 2,429 29-12-2018, 06:07 AM
Last Post:
  disadvantages of smart dustbin 0 644 27-10-2018, 03:47 PM
Last Post: Guest
  foot step bearing information advantages disadvantages application 0 684 21-10-2018, 08:54 PM
Last Post: Guest
  advantages n disadvantages of bhakra dam 0 652 03-10-2018, 08:04 PM
Last Post: Guest
  algorithm of railway reservation system 0 667 02-10-2018, 10:50 PM
Last Post: Guest
  advantages and disadvantages mains failure alarm circuit in pdf 0 780 01-10-2018, 11:48 PM
Last Post: Guest
  advantages and disadvantages of natural resources wikipedia 0 673 20-09-2018, 03:09 PM
Last Post: Guest

Forum Jump: