• 0ops@piefed.zip
    link
    fedilink
    English
    arrow-up
    4
    ·
    16 minutes ago

    Here’s the scientific article: https://arxiv.org/pdf/2504.17033

    The abstract (emphasis mine):

    We give a deterministic O(m log2/3 n)-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 O(m + n log n) time bound of Dijkstra’s algorithm on sparse graphs, showing that Dijkstra’s algorithm is not optimal for SSSP

    So this article’s a bit clickbaity in that this algorithm only outperforms Dijkstra’s in those specific cases, which aren’t uncommon, but Dijkstra’s is still king for undirected graphs, or graphs with negative edge weights. Still very neat.