Dijkstra’s Algorithm

The Dijkstra’s Algorithm created by Edsger Wybe Dijkstra (1930 – 2002) solves the shortest path problem, and is one of the most popular algorithms in computer science. In 1959, Dijkstra’s 3 pages long paper titled: “A Note on Two Problems in Connexion with Graphs”, was published in the journal Numerische Mathematik (1, 269-271). In this paper, Dijkstra proposed algorithms that help find shortest path between graph vertices in a graph. In most literature the Dijkstra’s algorithm is described as a greedy algorithm.

Dijkstra’s algorithm can be used to find the most low-cost path i.e. a cheaper way to transport an object to a destination from a source. However, before we use Dijkstra’s algorithm, let’s have a quick look on digraphs (directed graphs).

Directed graphs have oriented edges, where nodes are connected by these edges. A directed graph can be defined as a pair G = (V, E), V is a set of vertices, and E is the set of edges, see illustration below:

Now, with that covered let’s have some fun with the Dijkstra’s algorithm, shall we? Of course we will.

I’ll try to keep it simple, so I made a graph with paths from A to F, and each available choice has a cost, and we will chose the cheapest paths available, see graph below.

Once solved, it should look like this inside a table:

This symbol  means infinity. In the last choice, I went from D to F, the cost was an additional +20, meaning that in total it becomes 100, and 100 is always better than infinity.

If something isn’t clear, feel free to send me an e-mail, via: http://www.itknowledge24.com/contact.php.

Let me explain furthermore, how the Dijkstra’s algorithm works? Dijkstra’s algorithm works by solving the shortest path problem, it does this by computing the shortest path from the source to vertices among the closest vertices available to the source. For the Dijkstra’s algorithm to work and operate normally, the edges should be non-negative, if however, negative edges exist, Dijkstra’s algorithm will ultimately fail because shorter paths cannot be obtained, resulting in EPIC fail. In simple and short terms, the algorithm works by keeping shortest distance between vertex (V) from the source in an array and iterating until solved.

In conclusion, the Dijkstra’s algorithm is used almost everywhere—for example, the algorithm is used in the following areas:

  • Traffic Information Systems
  • Mapping (Google Maps or other mapping services or software)
  • Routing Systems

References:
http://www.cs.utexas.edu/~EWD/ 
http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf

For further reading, I recommend, MathWorld,
http://mathworld.wolfram.com/DijkstrasAlgorithm.html
and http://mathworld.wolfram.com/DirectedGraph.html

Leave a Reply