Feed: Slashdot
Feed Link: https://slashdot.org/
---

Title: New Method Is the Fastest Way To Find the Best Routes

Link: https://science.slashdot.org/story/25/08/08/1...

Computer scientists at Tsinghua University and Stanford have developed an
algorithm that surpasses a fundamental speed limit that has constrained
network pathfinding calculations since 1984. The team's approach to the
shortest-path problem -- finding optimal routes from one point to all others
in a network -- runs faster than Dijkstra's 1956 algorithm and its
improvements by avoiding the sorting process that created the decades-old
computational barrier. Led by Ran Duan at Tsinghua, the researchers combined
clustering techniques with selective application of the Bellman-Ford
algorithm to identify influential nodes without sorting all paths by
distance. The algorithm divides graphs into layers and uses Bellman-Ford to
locate key intersection points before calculating paths to other nodes. The
technique works on both directed and undirected graphs with arbitrary
weights, solving a problem that stymied researchers after partial
breakthroughs in the late 1990s and early 2000s applied only to specific
weight conditions.

Read more of this story at Slashdot.

---
VRSS v2.1.180528