Time & Space Complexity of Dijkstra's Algorithm

Free Linux Book

Get FREE domain for 1st year and build your brand new site

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:

  1. Introduction to Dijkstra's Algorithm
  2. Case 1: Naive Implementation
    • Worst Case Time Complexity
    • Average Case Time Complexity
    • Best Case Time Complexity
  3. Case 2: Binary Heap + Priority Queue
    • Worst Case Time Complexity
    • Average Case Time Complexity
    • Best Case Time Complexity
  4. Case 3: Fibonacci Heap + Priority Queue
    • Worst Case Time Complexity
    • Average Case Time Complexity
    • Best Case Time Complexity
  5. 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