Breaking The Sorting Wall: New Fastest Route Finder Algorithm Explained

For years Dijsktra has been the golden standard for finding the shortest distance between two places. It has also been put to commercial use in GPS and Google Maps. A recent breakthrough in the field of algorithms has proved the existence of a deterministic time algorithm for single source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model which performs better than Dijsktra.

It has been completely explained in the paper: Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

Before jumping into the algorithm let’s get a short and simple understanding of what this paper has actually been about.

Photo by Scott Graham on Unsplash

What’s the Paper About?

The paper is about finding the shortest path in a network(graph).

Suppose you live in a city with roads(edges) and intersections(nodes/vertices) and you want to know what will be the shortest path to go from your house to every other place in your city.

The earlier most optimal approach to find this would have been to use the Dijsktra’s algorithm using a Fibonnaci heap, which would have given a time complexity O(m + nlogn).

This approach used to work as follows:

• Maintain a priority queue of nodes, keyed by their current shortest distance estimate.
• Repeatedly extract the minimum-distance node (u).
• Relax all outgoing edges (u, v).
• Update neighbors’ distances in the priority queue.

Bottleneck of This Approach

The bottleneck in Dijkstra’s algorithm for sparse graphs (m ≈ n) is the priority queue’s need to maintain a sorted order of nodes by distance. Each extract-min (to pick the next node) and decrease-key (to update distances) operation takes log n time. With about n nodes and m ≈ n edges, you perform roughly n + m such operations, leading to a total time of n log n, which dominates the algorithm’s performance.

Photo by Deva Darshan on Unsplash

New Approach Explained In The Paper

They found a new way that is faster than Dijkstra’s for certain cases (sparse graphs — cities where there aren’t too many roads compared to intersections).

Their algorithm runs in O(m log^(2/3) n) time. That means it beats the old n log n barrier.

Get Akanksha Raj’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

This is exciting because people thought Dijkstra’s algorithm was basically the best possible in this setting.

Approach:

1. Start with the source (your house).
   Set its distance to 0. All others are “infinity” (unknown, really far).
2. Keep a frontier (the edge of what you know).
   These are the “cities” you’ve reached but haven’t fully explored.
   Normally Dijkstra would keep this frontier fully sorted (slow).
   Here, we’ll shrink it cleverly.
3. Find pivots (important leaders).

• Look at the frontier.
• Run a few (k) rounds of Bellman-Ford–style relaxations.
• This tells us which nodes already have their shortest paths done.
• For the remaining ones, only keep the few “leaders” whose subtrees are big.
• These leaders are the pivots.
• The rest can wait.

4. Divide and conquer.

• Take the pivots and split the problem into smaller chunks:
  “Let’s solve the shortest paths for this batch of closer nodes first, then move on to the next batch.”
• Each chunk is solved recursively: repeat the same “find pivots → shrink → solve” idea inside each subproblem.

5. Bounded Multi-Source Shortest Paths (BMSSP).

• Fancy name for a helper step: given several starting points (the pivots), find all nodes you can reach up to a certain distance B.
• If the work gets too big, stop early and set a new smaller boundary B’, then continue later.
• This keeps the workload under control.

6. Relax edges

• Each time you finish a group of nodes, relax their outgoing edges (like Dijkstra does).
• But instead of throwing everything back into a big heap, you only insert a limited number of candidates using a special data structure that’s faster than sorting everything

7. Use Recursion

• Keep shrinking, pivoting, and dividing.
• Eventually, every node gets its shortest distance confirmed.
• Because we never fully sort the whole set, we avoid the n log n bottleneck.

In Simple Words:

Imagine you’re trying to line up 1,000 kids by height:

1. Dijkstra = sort all 1,000 perfectly → slow.

2. New algorithm:

• Take groups of ~100
• pick only the tallest kid in each group (pivots)
• sort just them
• then handle their groups separately

This cuts out tons of wasted effort.

Summary of Steps:

• Start from the source, distance = 0.
• Keep a frontier of candidates.
• Shrink frontier using pivots (leaders).
• Solve subproblems with BMSSP (bounded shortest paths).
• Relax edges from completed nodes.
• Recurse until all nodes are complete.
• Done — you have all shortest paths!