Today's algorithm that I will be learning is Dijkstra's Algorithm. Before deciding to learn this algorithm I was thinking of learning some other algorithm becuase of the use of Graph and Nodes etc in this algorithm that I don't know about but then I decided to just try to learn this first and then see if those things are important to learn for this algorithm or not. So here I am trying to learn Dijkstra's Algorithm.
Image Courtesy: Wikipedia
Dijkstra's Algorithm
Dijkstra's Algorithm is a single-source shortest path-finding algorithm. It searchs for shotest path between Nodes in a Graph. A simple example for a Graph can be a network of roads and every turn on that road is a node and you have to find the shortest path to reach from point A to point B.
Path-Finding algorithms are used everywhere nowadays, from deciding what route a packet takes to reach its destination computer on the internet to Google maps to satelite navigation etc.
Dijkstra's Algorithm was invented by Dutch Computer Scientist Edsger Dijkstra in 1956. It is one of the most popular and widely used path-finding algorithms in the world. In an interview, Dijkstra said that he invented the Algorithm in just 20 Minutes.
How It Works?
Consider we have a network of roads or a Graph which have different nodes that connect all the roads with each other. We now select the source node from which we will start out path and a destination node to which we will end our path. The algorithm will follow the following steps.
- It checks the distance of all the nodes from the destination node and then keeps track of all the nodes checked with thier distance from the destination node.
- It will then check all other nodes that connect with the previous node and calculate their distance and tracks it with the name of the node.
- When it reaches the destination node it will back track it and follows the same steps with all other nodes until it reaches the destination node.
- Lastly it will look for the distances of all the paths between the source and destination node and tells us the shortest path.
The algorithm once it checks a node with the previous node is added to a list called visited list and will not be checked again.
Example
My explanaiton is so much confusing and maybe because I don't understand it very well myself and also an example would be a good way to exaplin it a bit more clearly but again the example will take more time and may not be more useful coming from me right now so why not let the pros explain it. Here are some sources to easily understand the Dijkstra's algorithm.
- Dijkstra's Algorithm - Computerphile
- Dijkstra Algorithm - Single Source Shortest Path - Greedy Method
- Dijkstra's Shortest Path Algorithm - A Detailed and Visual Introduction
Also the animated image above pretty much explains the algorithm all by itself but still the more detial the better.
zainsci