A new technique breaks Dijkstra's 70-year-old record: it finds routes faster in huge networks, changing graph theory forever.
  • jet@hackertalks.comEnglish
    4·
    3 months ago

    https://arxiv.org/abs/2504.17033

    We give a deterministic    -time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the   time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP.