Live and recent posts from across the Fediverse tagged #shortestpath, aggregated by home.social.
@AlSweigart ...or, when we talk about Dijkstra's algorithm, why not make it O(m log^(2/3) n)!? 😜
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths:
https://arxiv.org/abs/2504.17033
To achieve this, the researchers _combine_ Dijkstra’s algorithm with Bellman-Ford algorithm - incredible stuff! 🤓
New Method Is the Fastest Way To Find the Best Routes
https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/
> A canonical problem in computer science is to find the shortest route to every point in a network. A new approach beats the classic algorithm taught in textbooks.
The new algorithm for directed cheapest routes "slices the graph into layers, moving outward from the source like Dijkstra’s. But rather than deal with the whole frontier at each step, it uses the Bellman-Ford algorithm to pinpoint influential nodes, moves forward from these nodes to find the shortest paths to others, and later comes back to other frontier nodes. It doesn’t always find the nodes within each layer in order of increasing distance, so the sorting barrier doesn’t apply. And if you chop up the graph in the right way, it runs slightly faster than the best version of Dijkstra’s algorithm. It’s considerably more intricate, relying on many pieces that need to fit together just right. But curiously, none of the pieces use fancy mathematics."
https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/
#graphTheory #shortestPath #navigation #networks #computing #CS #computerScience #algorithmics #algorithmic #algorithms #algorithm
🚀 Behold, the revolutionary Yggdrasil: a "decentralized" #network that promises to find the shortest path in life, yet ironically takes the longest route to explain itself. 🌐 Because who doesn't want to spend hours setting up peering connections for an "experimental" adventure into network obscurity? 🙄
https://yggdrasil-network.github.io/about.html #Yggdrasil #Decentralization #ShortestPath #ExperimentalTech #NetworkSetup #HackerNews #ngated