An Elementary Analysis of Dijkstra’s Algorithm
A tale of woe experienced by almost every computer science engineer at least once in their life, Dijkstra’s Algorithm lives up to its reputation of being one of the most useful algorithms in Design and Analysis of Algorithms. Created by Edsger W. Dijkstra, an eminent physicist, the algorithm is use to obtain the shortest path in a graph or net and belongs to the family of greedy algorithms.
HOW DOES IT WORK?
Let us take a directed graph G = {N, E}, where N is a set of nodes of G and E is the set of directed edges, with each edge having a non — negative length. We take one of the nodes as the origin node.
Additionally, we take two nodes S and C, where S holds the set of selected nodes [including the distance to the origin node at a given time] and C holds all the candidate nodes [whose distance is unknown]. From this, we derive the invariant property N = S ∪ C.
Initially, the set S has only the node — origin and when the algorithm finishes, it contains all the graph nodes along with their costs. The algorithm maintains a matrix D that is updated at each step with the weights of the shortest special path of each node of set S.
PSEUDO CODE
EXAMPLE
To help us better understand Dijkstra’s algorithm, let us clarify things with a simple example.
By following the steps, we move from one node to another, while continuously updating matrices v, C and D.
Matrix D would not change even if one more interaction to remove the last element of C {2} was done, hence the main loop only repeats n-2 times.
TIME COMPLEXITY
For initialization → n O(n)
For repeat loop→ n² O(n²)
Therefore, for simple implementation→ O(n²)
MAIN AREAS WHERE DIJKSTRA’S ALGORITHM IS USED
Some applications for Dijkstra’s algorithm are :-
- Robot navigation
- Typesetting in TeX
- Urban traffic planning
- Tramp steamer problem
- Optimal pipelining of VLSI chip
- Telemarketer operator scheduling
- Subroutine in higher level algorithms
- Routing of telecommunications messages
- Approximating piecewise linear functions
- Open Shortest Path First (OSPF) routing protocol for IP
There are many more areas where this algorithm is used, however the ones listed give a good example of its wide variety of industry applications.
DIFFERENCE BETWEEN DIJKSTRA’S AND PRIM’S / KRUSKAL’S ALGORITHM
Dijkstra’s algorithm’s main focus is on optimizing the shortest path. This means that it does not consider it necessary to cover all the edges of the graph, but instead to reach all the nodes.
Prim’s algorithm and Kruskal’s algorithm on the other hand, focus on discovering the minimum coverage tree, i.e., how to cover the entire graph efficiently.
PROS AND CONS
PROS
- Uninformed algorithm
Dijkstra is an uninformed algorithm, meaning that it does not need to know the target node beforehand. For this reason, it’s preferred in cases where you don’t have any prior knowledge of the graph and when you do not know of the distance between each node and the target.
2. Good when you have multiple target nodes
Dijkstra focuses on picking edges with the smallest cost at each step and it usually covers a large area of the graph. This makes it especially useful when the graph has multiple target nodes, but it is not known which is the closest one.
CONS
- Fails for negative edge weights
This can be explained with the help of an example. Let us take 3 Nodes (A, B and C) where they form an undirected graph with edges: AB = 3, AC = 4, BC=-2. The optimal path from A to C costs 1 and the optimal path from A to B costs 2. If we apply Dijkstra’s algorithm, we will start from A and then examine B because it is the closest node. We will assign a cost of 3 to it and mark it closed, which means that its cost will never be reevaluated. This means that Dijkstra’s cannot evaluate negative edge weights.
CONCLUSION
After going through the blog, it can be summarized that Dijkstra’s algorithm has a wide variety of important uses due to its focus on finding the shortest optimized path to reach all nodes. However, it is not omnipotent as it does have problems with negative weights for the edges.
Thank you for reading!
— Arhant Bhatt
