Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we have explored the Time & Space Complexity of Dijkstra's Algorithm including 3 different variants like naive implementation, Binary Heap + Priority Queue and Fibonacci Heap + Priority Queue.
Table of contents:
- Introduction to Dijkstra's Algorithm
- Case 1: Naive Implementation
- Worst Case Time Complexity
- Average Case Time Complexity
- Best Case Time Complexity
- Case 2: Binary Heap + Priority Queue
- Worst Case Time Complexity
- Average Case Time Complexity
- Best Case Time Complexity
- Case 3: Fibonacci Heap + Priority Queue
- Worst Case Time Complexity
- Average Case Time Complexity
- Best Case Time Complexity
- Overview
Prerequisite: Dijkstra's Algorithm, Binary Heap, Fibonacci Heap
Introduction to Dijkstra's Algorithm
Dijkstra's Algorithm is a pathfinding algorithm, used to find the shortest path between the vertices of a graph. It is one of the most popular pathfinding algorithms due to its diverse range of applications. In this article we will be analysing the time and space complexities in different use cases and seeing how we can improve it.
The algorithm works for the following scenarios:
- Directional and non-directional graphs
- Weighted edges
- Graph is connected
Case 1: Naive Implementation
This is our simplest implementation as well as the least efficient. In this approach, using an unsorted array, we search through all vertices to find the closest within the graph. This means that our initial time complexity will be O(n) for this search. This will bring our total time complexity to O(V^2) where is the number of vertices in the graph. Space complexity will be O(V) where V is number of vertices in graph, it is worse case scenario if it is a complete graph and every edge has to be visited.
- Create a set with all vertices as unvisted called unvisited set.
- Assign each vertex a distance cost, 0 for the root node and infinity for the rest, set root node as current node
- For the current node (i), find all of its neighbours and calculate their costs by adding the edge weights connecting current node and neighbour (j) to the current nodes cost (i -> j + i)
- Once all neighbours have been checked, mark the current node as unvisited and place it to the visited set, this set will never be rechecked
- Once all vertices have been added to visited set, the algorithm has complete
- If not, repeat steps 3-5 until all nodes have been visited
Implementation in Pseudocode
COST = 0
PREVIOUS = 1
FUNCTION dijkstras(graph, start_node)
unvisited = {}
visited = {}
FOR key IN graph
unvisited[key] = [infinity, NULL]
NEXT key
unvisited[start_node][COST] = 0
finished = False
WHILE finished == False
IF LEN(unvisited) == 0
finished = True
ELSE
current_node = minimum(unvisited)
FOR neighbour IN graph[current_node]
IF neighbour NOT IN visited
cost = unvisited[current_node][COST] + graph[current_node][neighbour]
IF cost < unvisited[neighbour][COST]
unvisited[neighbour][COST] = cost
unvisited[neighbour][PREVIOUS] = current_node
ENDIF
ENDIF
NEXT neighbour
visited[current_node] = unvisited[current_node]
DEL(unvisited[current_node])
ENDIF
ENDWHILE
RETURN visited
ENDFUNCTION
Worst Case Time Complexity
As stated above this is the worst case complexity for Dijkstra's algorithm with O(V^2) when implementing using an unsorted array and no priority queue. This is because for each vertex (V), we need to relax the connected edges in order to find the minimum cost edge that connects a vertex to V. We need to do V number of calculations and each operation takes O(V) times, therefore leaving us with the complexity of O(V^2)
- V calculations
- O(V) time
Total: O(V^2)
Average Case Time Complexity
The average case doesn't change the steps we have to take since the array isn't sorted, we do not know the costs between each node. Therefore it will remain O(V^2) since
- V calculations
- O(V) time
Total: O(V^2)
Best Case Time Complexity
The same situation occurs in best case since again the array is unsorted:
- V calculations
- O(V) time
Total: O(V^2)
Case 2: Binary Heap + Priority Queue
To improve our intial implementation of the algorithm, we can switch to using a priority queue and a binary heap instead of the unsorted array. We include an adjaceny list in the heap for efficient indexing. For this, we need to take the following steps:
- Create V binary heap, where V is the number of vertices in our graph. This contains our adjacency list: The vertex number and its cost
- Root vertex distance = 0, all others = infinity
- Condition controlled loop whilst heap is not empty:
- Find vertex with lowest distance cost from binary heap (i)
- For all adjacent vertices (j) to lowest cost vertex, check if they are in heap.
- If in heap and distance value is more than distance i -> j + i, update distance of j
Here are common heap operations and their time complexities using binary heap:
| Operation | Time Complexity |
|---|---|
| Insert | O(logN) |
| ReturnMin | O(1) |
| DeleteMin | O(logN) |
| Delete | O(logN) |
| DecreaseKey | O(logN) |
| Merge | O(1) |
Implementation in Python
from collections import defaultdict
import heapq
def bin_heap_dijkstras(times : list[list[int]], x : int, y : int) -> int:
graph = defaultdict(dict)
for src, dest, cost in times:
graph[src][dest] = cost
distance_costs = {i: float("inf") for i in range(1, x + 1)}
distance_costs[y] = 0
min_dist = [(0,x)]
visited = {}
while min_dist:
current_dist, current = heapq.heappopp(min_dist)
if current in visited:
continue
visited.add(current)
for neighbour in graph[current]:
if neighbour in visited:
continue
checking_dist = current_dist + graph[current][neighbour]
if checking_dist < distance_costs[neighbour]:
distance_costs[neighbour] = checking_dist
heapq.heappush(min_dist, (checking_dist, neighbour))
if len(visited) != len(distance_costs):
return -1
return distance_costs[max(distance_costs, key=distance_costs.get)]
This implemenation uses the library heapq for our priority queue operations and its complexities are explained below:
Worst Case Time Complexity
Our inner loop statements occur O(V + E) times, where V is number of vertices and E is number of edges, with the decrease key operation taking O(logV) meaning the total time complexity for our implementation is O((V + E)*logV) as E -> V this simplifies to O(ElogV). Where we have the largest number of decrease key operations (which take logV).
- Inner loop operations O(V + E) times
- Decrese key takes O(logV)
Total O(ElogV) where decrease key happens the most amount of times
Average Case Time Complexity
The average running time in this case will be O(EVlog(E/V)logV). We know this since our inner loop still takes O(V + E) times, the only difference is the amount of decrease key operations is bounded by O(Vlog(E/V)) meaning that there is a constant on the calculations.
- Inner loop operations O(V + E) times
- Decrese key takes O(logV)
Total O(EVlog(E/V)logV) where decrease key happens O(log(E/V) times
Best Case Time Complexity
Our best case is identical to our worst case however it is when the number of key operations are the smallest. this means we will have a complexity of O(ElogV) still, just will the number of logV operations reduced.
- Inner loop operations O(V + E) times
- Decrese key takes O(logV)
Total O(ElogV) where decrease key happens the least amount of times
Inner loop operation time complexities can be found in table shown above
Case 3: Fibonacci Heap + Priority Queue
Our final implementation of Dijkstra's is our most efficient. A fibonacci heap is a lazy data structure, meaning that common operations carried out on the heap are very fast due to the structure being less managed whilst its performing actions. For a fibonacci heap here are the time complexities of the same common operations as we saw in binary heap:
| Operation | Time Complexity |
|---|---|
| Insert | O(1) |
| ReturnMin | O(1) |
| DeleteMin | O(logN) |
| Delete | O(logN) |
| DecreaseKey | O(1) |
| Merge | O(1) |
The reason why we are able to have O(1) for many operations as a apposed to in a binary heap is the nature of the fibonacci. Each node contains a pointer to its parent and one of its children. We then can use a circular linked list to connect the children nodes. Since there is always a pointer to the minimum distance value node in the heap meaning we get an extremely efficient time frame for many actions.
Implementation explanation
The fibonacci heap is largely theoretical in it's implementation due to its high programming complexity leading to it actually performing worse in some cases and applications (like sparse graphs) than our binary tree, however it has the conceptual potential to have the best efficiency do to the high connections between the nodes.
Our total time complexity for our this approach is O(VlogV + E), where V is number of vertices and E is number of edges. As stated above, this is our most efficient case for the Dijkstra's Algorithm.
Worst Case Time Complexity
The same steps occur in this algorithm as in the binary heap, however, the fibonacci heap can reduce our running time further since to increment a nodes priority now only takes O(1) time, instead of O(logV) like when using the binary heap. Meaning that our new worst case time would be O(E+VlogV), with the largest number of decrease key calculations.
- Inner loop operations O(V + E) times
- Decrese key takes O(1)
Total O(E+VlogV) where decrease key happens the most amount of times
Average Case Time Complexity
In the average case the fibonacci similar to the binary heap, we limit our number of key decreases by O(Vlog(E/V)). Multiplying this by our original complexity therefore gives us the average of O(E+Vlog(E/V)VlogV).
- Inner loop operations O(V + E) times
- Decrese key takes O(1)
Total O(E+Vlog(E/V)VlogV) where decrease key happens O(Vlog(E/V) amount of times
Best Case Time Complexity
Similarly to our binary heap implementation, the worst and best case scenarios for fibonacci heap have the same base complexity, the difference being the amount of decrease key operations. This means we will have a complexity of O(E+VlogV), with the smallest amount of O(1) operations for the graph.
- Inner loop operations O(V + E) times
- Decrese key takes O(1)
Total O(E+VlogV) where decrease key happens the least amount of times
Inner loop operation time complexities can be found in table shown above
Overview
In this article we have analysed multiple different use cases of Dijkstra's Algorithm and derived the complexities for each method, getting more efficient in each case, we can see how changing the internal data structure used in the algorithm has an effect on the efficiency.
From our research about Dijkstra's, we can say:
Naive:
Best Case: O(V^2)
Average Case: O(V^2)
Worst Case: O(V^2)
Binary Heap:
Best Case: O(ElogV) (smallest number of decrease key operations)
Average Case: O(EVlog(E/V)logV) (Average number of key decreases: O(Vlog(E/V)))
Worst Case: O(ElogV) (largest number of decrease key operations)
Fibonacci Heap:
Best Case: O(E+VlogV) (smallest number of decrease key operations)
Average Case: O(E+Vlog(E/V)VlogV) (Average number of key decreases: O(Vlog(E/V)))
Worst Case: O(E+VlogV) (largest number of decrease key operations)
Space complexity: O(V) for all
