#shortestpath — Public Fediverse posts

@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! 🤓

@shanecelis

#Algorithm #Algorithms #Paper #ShortestPath #Dijkstra

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

#arxivfeed :

"Comparing models of information transfer in the structural brain network and their relationship to functional connectivity: Diffusion versus shortest path routing"
https://www.biorxiv.org/content/10.1101/2022.11.11.515707v1

#neuroscience #neuro #brain #network #connectome #connectivity #graph #GraphTheory #DTI #fMRI #DiffusionModel #ShortestPath