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