Edsger Dijkstra published Dijkstra’s algorithm in 1959, implemented over a weighted graph, to find the shortest path, but how it works, read in the blog
A Dutch computer scientist, Edsger Dijkstra, in 1959, proposed an algorithm that can be applied to a weighted graph. The graph can either be directed or undirected with the condition that the graph needs to embrace a non-negative value on its every edge. He named this algorithm “Dijkstra’s Algorithm” at his name.
What if you are provided with a graph of nodes where every node is linked to several other nodes with varying distance. Now, if you begin from one of the nodes in the graph, what is the shortest path to every other node in the graph?
Well simply explained, an algorithm that is used for finding the shortest distance, or path, from starting node to target node in a weighted graph is known as Dijkstra’s Algorithm. This algorithm makes a tree of the shortest path from the starting node, the source, to all other nodes (points) in the graph.
Dijkstra’s algorithm makes use of weights of the edges for finding the path that minimizes the total distance (weight) among the source node and all other nodes. This algorithm is also known as the single-source shortest path algorithm. (Also read: 7 Major Branches of Discrete Mathematics)
Dijkstra’s algorithm is the iterative algorithmic process to provide us with the shortest path from one specific starting node to all other nodes of a graph. It is different from the minimum spanning tree as the shortest distance among two vertices might not involve all the vertices of the graph.
It is important to note that Dijkstra’s algorithm is only applicable when all weights are positive because, during the execution, the weights of the edges are added to find the shortest path.
And therefore if any of the weights are introduced to be negative on the edges of the graph, the algorithm would never work properly. However, some algorithms like the Bellman-Ford Algorithm can be used in such cases.
It is also a known fact that breadth-first search(BFS) could be used for calculating the shortest path for an unweighted graph, or for a weighted graph that has the same cost at all its edges. But if the weighted graph has unequal costs at all its edges, then BFS infers uniform-cost search.
Now what? Instead of extending nodes in order of their depth from the root, uniform-cost search develops the nodes in order of their costs from the root. And a variant of this algorithm is accepted as Dijkstra’s Algorithm.
Generally, Dijkstra’s algorithm works on the principle of relaxation where an approximation of the accurate distance is steadily displaced by more suitable values until the shortest distance is achieved.
Also, the estimated distance to every node is always an overvalue of the true distance and is generally substituted by the least of its previous value with the distance of a recently determined path.
It uses a priority queue to greedily choose the nearest node that has not been visited yet and executes the relaxation process on all of its edges.
Advantages of Dijkstra’s algorithm;
- One of the main advantages of it is its little complexity which is almost linear.
- It can be used to calculate the shortest path between a single node to all other nodes and a single source node to a single destination node by stopping the algorithm once the shortest distance is achieved for the destination node.
- It only works for directed-, weighted graphs and all edges should have non-negative values.
Dijkstra’s algorithm has disadvantages also, such as;
- It does an obscured exploration that consumes a lot of time while processing,
- It is unable to handle negative edges,
- As it heads to the acyclic graph, so can’t achieve the accurate shortest path, and
- Also, there is a need to maintain tracking of vertices, have been visited.