Time Complexity of Single-Source Shortest Path Algorithms

Graph data structures are widely used to represent different aspects of computer science (e.g., road networks). We can denote a graph as \(G = (V, E)\), where \(V\) represents the set of vertices (in the context of a road network, these represent intersections), and \(E\) represents the set of edges (representing road segments). We generally define \(n~(= |V|)\) as the number of vertices and \(m~(= |E|)\) as the number of edges to express the time and space complexity of graph algorithms. One such problem is single-source shortest path (SSSP), which is used to find the shortest path from a single node to all other nodes. For decades, Dijkstra’s algorithm has been the go-to method for solving this problem. The runtime of Dijkstra’s algorithm depends on the priority queue implementation and often has a complexity of \(O(m + n \log n)\).

The New Algorithmic Breakthrough [Refer: Arxiv]

Recently, researchers proposed a new algorithm that challenges the long-standing dominance of Dijkstra. The key highlight is the reduced complexity of the new algorithm, with a computational complexity of

This is strictly better asymptotically than Dijkstra’s \(O(m + n \log n)\) bound, especially for sparse graphs where \(m\) is closer to \(n\).

We can express the time complexity using simple functions as follows:

1. \(O(n \log n + m)\) may actually take \(k_1 \cdot n \log n + k_2 m\) computational units, where \(k_1, k_2\) are problem-independent constants
2. \(O(m \log^{2/3} n)\) may actually take \(k_3 \cdot m \log^{2/3} n\) computational units, where \(k_3\) is a problem-independent constant

In order to make the new algorithm more efficient, we need to identify the maximum value of \(m\) such that the proposed approach outperforms Dijkstra. Accordingly, we can formally express the inequality to determine the maximum value of \(m\) as follows:

Accordingly, \(m\) should satisfy the following constraint for the new approach to outperform Dijkstra:

For simplicity, let us assume all problem-independent constants equal \(1\). Accordingly, \(m\) should satisfy the following inequality for the new approach to outperform Dijkstra:

The figure below shows how the number of edges (\(m\)) varies for various node values (\(n\)):

We observe that around \(n = 1000\), \(m \approx 2744\). The above figure can be obtained from the following code:

import math
import matplotlib.pyplot as plt

node_values = [2 ** k for k in range(2, 13)]
edge_values = []
for n in node_values:
    edge_value = n * math.log(n, 2) / (math.pow(math.log(n, 2), 2/3)  - 1)
    edge_values.append(edge_value)

plt.plot(node_values, edge_values)
plt.grid(which="major", alpha=0.5, linewidth=1)
plt.yscale('log')
plt.xlabel('Number of Nodes (n)')
plt.ylabel("Number of Edges (m)")
plt.show()

We can define the density of graph \(G\) as \(Den(G) = \frac{2m}{n \cdot (n + 1)}\), which gives the ratio between the number of edges in the graph (\(m\)) and the maximum possible number of edges if all nodes were connected to every other node (i.e., \(\frac{n \cdot (n + 1)}{2}\)).

Substituting \(m = \frac{Den(G) \cdot n \cdot (n + 1)}{2}\) into the above inequality gives the relationship between the maximum allowed graph density for a given number of nodes:

Moving all \(n\) (\(n \geq 1\)) to the right-hand side, we obtain:

The figure below shows how the maximum graph density (\(Den(G)\)) varies for various node values (\(n\)):

We observe that around \(n = 1000\), \(Den(G) \approx 0.0055\) and \(m \approx 2744\). This signals how sparse a network needs to be for the new algorithm to outperform Dijkstra. The above figure can be obtained from the following code:

import math
import matplotlib.pyplot as plt

node_values = [10 ** k for k in range(1, 13)]
density_values = []
for n in node_values:
    density_value = 2 * math.log(n, 2) / ((n + 1) * (math.pow(math.log(n, 2), 2/3)  - 1))
    density_values.append(density_value)

plt.plot(node_values, density_values)
plt.grid(which="major", alpha=0.5, linewidth=1)
plt.xscale('log')
plt.xlabel('Number of Nodes (n)')
plt.ylabel("Graph Density (Den(G))")
plt.show()

This is generally reasonable for road networks, where not every node (i.e., intersection) is connected to every other node via road segments. In practice, most intersections connect to only a handful of nearby roads, making real-world road networks sparse graphs. This sparsity is exactly why the proposed new algorithm with time complexity \(O(m \log^{2/3} n)\) can yield reasonable performance gains over Dijkstra, especially as the network scales to tens or hundreds of thousands of nodes. For example, in Chattanooga, TN, the road network from OpenStreetMap has \(n = 10{,}788\) and \(m = 28{,}100\) (Refer: Paper); based on the above expression, \(m\) can go up to \(31{,}142\). Note that we simplified the inequality by setting all independent constants \(k_1, k_2, k_3\) to 1, so this evidence alone may not be sufficient to support the above claim.