Dijkstra's algorithm
Introduction
Dijkstra's algorithm is a graph theory algorithm that solves the shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms. It was conceived by computer scientist Edsger Dijkstra in 1956 and published three years later.
Description
Dijkstra's algorithm uses a priority queue to greedily select the closest node that has not yet been processed, and performs this relaxation process on all of its outgoing edges; thus, when we complete the process, we have solved the single-source shortest path problem.
The algorithm maintains a set S of vertices whose final shortest-path weights from the source s have already been determined. The algorithm repeatedly selects the vertex u ∈ V - S with the minimum shortest-path estimate, inserts u into S, and relaxes all edges leaving u. In the following code, we assume that the graph G = (V, E) is represented by adjacency lists.
Algorithm
The algorithm is often implemented as follows in pseudocode:
1. Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty. 2. Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign distance value as 0 for the source vertex so that it is picked first. 3. While sptSet doesn’t include all vertices
a. Pick a vertex u which is not there in sptSet and has minimum distance value. b. Include u to sptSet. c. Update distance value of all adjacent vertices of u. For every adjacent vertex v, if sum of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.
Time Complexity
The time complexity of Dijkstra’s algorithm is O(V^2). However, the time complexity can be reduced to O(E log V) using binary heap. Here, E is the number of edges in the graph and V is the number of vertices. This is because, every vertex is removed once and added once to the priority queue. Also, for every vertex, we iterate over its adjacent vertices.
Applications
Dijkstra's algorithm is widely used in network routing protocols, most notably IS-IS (Intermediate System to Intermediate System) and OSPF (Open Shortest Path First). These are used in Internet backbone networks, and IS-IS is also used in some enterprise networks. Other applications include determining the shortest path for delivery trucks, telephone network routing, and in software for drawing tool paths for circuit board and metal cutters.
Limitations
Despite its importance and broad applicability, Dijkstra's algorithm has several important limitations:
1. It fails to handle graphs with negative weight edges: Dijkstra's algorithm assumes that the edge weights are non-negative. This is because it is a greedy algorithm and makes the decision based on current best option. If the graph has negative weight edges, the decision made by the algorithm may not be optimal.
2. It does not work for distributed systems: Dijkstra's algorithm requires global knowledge of the graph. In a distributed system where each node knows only about its neighbours, it is impossible to implement Dijkstra's algorithm.
3. It is not suitable for real-time systems: The algorithm is not efficient for large graphs because it needs to maintain a priority queue of vertices. This makes it unsuitable for real-time systems where time efficiency is critical.
Variations
There are many variations of Dijkstra's algorithm that are designed to overcome its limitations, to improve its performance, or to make it more suitable for a particular problem. Some of these variations include the A* search algorithm, Bellman-Ford algorithm, Johnson's algorithm, and Fibonacci heap Dijkstra's algorithm.