New Method Is the Fastest Way To Find the Best Routes

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.