Dijkstra Breakthrough: Breaking the 41-Year Sorting Barrier

Go implementation of the revolutionary shortest-path algorithm that breaks the 41-year sorting barrier in graph algorithms.

🏆 About

This package implements the breakthrough shortest-path algorithm from the STOC 2025 Best Paper:

"Breaking the Sorting Barrier for Directed Single-Source Shortest Paths" Authors: Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin (Tsinghua University) ArXiv: https://arxiv.org/abs/2504.17033

Key Achievement

First deterministic algorithm to achieve O(m log^(2/3) n) time complexity for single-source shortest paths on directed graphs with non-negative weights, breaking Dijkstra's O(m + n log n) barrier that stood for 41 years.

📦 Installation

go get github.com/lib-x/dijkstrabreakthrough-go

🚀 Quick Start

package main

import (
    "fmt"
    "log"

    "github.com/lib-x/dijkstrabreakthrough-go"
)

func main() {
    // Create a graph with 5 vertices
    graph, err := dijkstra.NewGraph(5)
    if err != nil {
        log.Fatal(err)
    }

    // Add edges
    _ = graph.AddEdge(0, 1, 4.0)
    _ = graph.AddEdge(0, 2, 1.0)
    _ = graph.AddEdge(2, 1, 2.0)
    _ = graph.AddEdge(1, 3, 1.0)
    _ = graph.AddEdge(2, 3, 5.0)
    _ = graph.AddEdge(3, 4, 3.0)

    // Run the breakthrough algorithm
    result, err := dijkstra.BreakthroughAlgorithm(graph, 0)
    if err != nil {
        log.Fatal(err)
    }

    // Print results
    result.PrintResults(0)

    // Get path to a specific vertex
    path, _ := result.Path(4)
    fmt.Printf("Shortest path from 0 to 4: %v\n", path)
    fmt.Printf("Distance: %.2f\n", result.Distances[4])
}

📚 Algorithms Implemented

1. Traditional Dijkstra's Algorithm

Complexity: O(m + n log n)

result, err := dijkstra.TraditionalDijkstra(graph, source)

2. Breakthrough Algorithm (Simplified)

Complexity: O(m log^(2/3) n) [theoretical]

result, err := dijkstra.BreakthroughAlgorithm(graph, source)

3. Bellman-Ford Algorithm

Complexity: O(mn)

result, err := dijkstra.BellmanFord(graph, source)

💡 Usage Examples

Example 1: Basic Usage

graph, _ := dijkstra.NewGraph(5)
_ = graph.AddEdge(0, 1, 4.0)
_ = graph.AddEdge(0, 2, 1.0)

result, _ := dijkstra.TraditionalDijkstra(graph, 0)
fmt.Printf("Distance to vertex 1: %.2f\n", result.Distances[1])

Example 2: Compare Algorithms

graph, _ := dijkstra.NewTestGraph("sparse", 1000)

dijkstraResult, _ := dijkstra.TraditionalDijkstra(graph, 0)
breakthroughResult, _ := dijkstra.BreakthroughAlgorithm(graph, 0)

fmt.Printf("Dijkstra: %.3f ms\n", dijkstraResult.ExecutionTimeMillis())
fmt.Printf("Breakthrough: %.3f ms (%.2fx speedup)\n",
    breakthroughResult.ExecutionTimeMillis(),
    dijkstraResult.ExecutionTimeMillis() / breakthroughResult.ExecutionTimeMillis())

Example 3: Path Reconstruction

result, _ := dijkstra.TraditionalDijkstra(graph, 0)
path, _ := result.Path(5)
fmt.Printf("Path: %v, Distance: %.2f\n", path, result.Distances[5])

🧪 Running Examples and Tests

Run the demo:

cd cmd/demo
go run main.go

Run the basic usage example:

cd examples
go run basic_usage.go

Run all tests:

go test -v

Run benchmarks:

go test -bench=. -benchmem

📝 Important Notes

About This Implementation

Simplified Conceptual Implementation: This package demonstrates the key breakthrough concepts:

• Frontier-based clustering
• Batch vertex processing
• Dynamic frontier pruning
• Hybrid relaxation strategy

Full Research Algorithm (Experimental):

• ✅ NOW AVAILABLE in research_algorithm/ package
• Implements all core components from the paper:
  • Red-Black tree for block management
  • Block-based linked lists (Lemma 3.3)
  • BaseCase (Algorithm 2)
  • FindPivots (Algorithm 1)
  • BMSSP recursive procedure (Algorithm 3)
• Status: Experimental, works for simple graphs
• See research_algorithm/README.md for details

🔬 Research Citation

@inproceedings{duan2025breaking,
  title={Breaking the Sorting Barrier for Directed Single-Source Shortest Paths},
  author={Duan, Ran and Mao, Jiayi and Mao, Xiao and Shu, Xinkai and Yin, Longhui},
  booktitle={STOC 2025},
  year={2025},
  note={Best Paper Award}
}

📜 License

MIT License

🌟 Acknowledgments

Original research by Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, and Longhui Yin from Tsinghua University (STOC 2025 Best Paper Award).