New Method Is the Fastest Way To Find the Best Routes (quantamagazine.org) 51
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.
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.
This is my jam! (Score:4, Interesting)
I love compsci and am thrilled to see that there is still progress being made on problems like this.
There are other problems with solutions that are conjectured (but not proven) to be at their limit for efficiency. One such problem is the subset-sum problem, and of course there's the 3-SAT problem (NP complete.)
Re: (Score:1)
This was one of my most favourite ComSci side projects. I took a image bitmap read write code project from a graphics class and combined it with a shortest route algorithm from another class. Together I was able to scan a city map, use each pixel as a unit and calc the shortest route. It was so much fun.
Re:This is my jam! (Score:4, Interesting)
If that is your thing, I hope you have seen what AlphaEvolve has done "in 20% of cases, AlphaEvolve improved the previously best known solutions":
https://deepmind.google/discov... [deepmind.google]
I think we will be seeing a lot more of new discoveries made by AI in the near future.
Travelling salesmen (Score:2)
Re: (Score:2)
Maybe one day yet that salesman may be able to come home to his wife and kids.
Re: Travelling salesmen (Score:2)
no I heard he's dead.
Re: (Score:2)
Might be, we'll have to go around investigating his itinerary's cities one by one and see if these rumors of his death are exaggerated.
Hey, we could probably save on fuel and time by planning our route first, avoid revisits and such, anyone know if there's a good way to do that...
Re: (Score:3)
Re: (Score:3)
He's making a reference to "Death of a Salesman"
Re: (Score:3)
Re: (Score:2)
no I heard he's dead.
No, he's just resting; all shagged out from a long trip.
Re: (Score:2)
The traveling salesman needs to leave home first. His quota included too many cities, so he's still waiting for a solution.
Re: (Score:2)
Given that AFAIK there is no formal analytical solution for the TS problem, only ones that work darned well but are empirical, how much "better" does this approach do compared to the additional effort required? There's a benefit/cost issue.
Re: (Score:1)
Re: (Score:3)
Re: (Score:2)
Re: Travelling salesmen (Score:3)
I don't think squaring the circle is a good example here, since the problem isn't so much a find the number problem, but a find the answer while restricting yourself to a few specific operations problem. So the non-algebraic solution doesn't count because it doesn't follow the rules. People knew what the answer was as a number that you can calculate for ages. They weren't sure if you could do it while following the arcane rules of ancient compass and straightedge constructions. It's turns out that the answe
Re: (Score:2)
Re: (Score:1)
Not sure what you mean by darned well and empirical, but I'll give my understanding:
There are TSP solvers that don't merely work darned-well, they give an exact solution and use optimizations like early-culling of permutations that are known not to be in the solution. It's still O(n!) but in practice, with optimizations, this is better than an exponential-time algorithm that needs n^2 space for large graphs. (Consider 2000 cities, an algorithm that requires 2^2000 bits of memory is impossible to execute.)
Th
Re: (Score:3)
Pick-and-place robots for circuit board assembly use path minimization algorithms.
The robot moves over a 2D PCB surface, placing components. Cutting a few seconds off the P&P time can mean big savings.
FPGA and ASIC layout engines also use these algorithms.
Re: (Score:2)
No.
TSP assumes you know the optimal distances between each pair of cities and then tries to find the perfect ordering such that the total distance is minimized. The TSP itself does not involve the steps to compute the optimal route between two cities.
Is this bad news for energy utilities? (Score:2)
By how much will electricity demand fall short of forecasts made using old constraints on algos?
Re: (Score:2)
How much faster? (Score:2)
Nowhere in the article does it say how much faster this is compared to the previous method. Are we talking second faster, milli-seconds faster, how much?
Re: (Score:3)
Re:How much faster? (Score:5, Informative)
Re: (Score:2)
Re:How much faster? (Score:5, Informative)
For a graph with 13 vertices, anything with more than 50 edges is faster with Dijkstra's.
For almost any algorithm, if you limit the input, you can create an algorithm that is faster on the subset of the input, but slower on other inputs. (my math might still be wrong don't publish it).
Re: (Score:2)
Okay I'll bite. I didn't spend a lot of time proof reading this and re-thinking it, but I think it works. Anyway, it's sketchy to say "for which" values of v and e, since the growth rate is asymptotic. But approximately for any particular implementation, we just set the growth rates equal.
Taking the complexities from:
https://arxiv.org/abs/2504.170... [arxiv.org]
We get that the two equalize at:
mlog(n)^{2/3}n = m + nlog n
If we switch m for y and n for x, and solve for y, we can write y as a function of x as:
y= \frac{y\lo
Re: (Score:1)
I accidentally switched to y's, that should have read x\logx / x\log(x)^{2/3} = log(x)^{1/3}.
Re: (Score:2)
Re: (Score:1)
I agree base 2 seems most natural in this context. Of course, if we do use different bases it just re-scales the growth by a constant factor via the base change formula, so I think it's probably just ignored for that reason (see first link). As for my notation, if you look under the section Using Common Logarithms in the OpenStax textbook section (see second link), you'll see a discussion on the meaning of "log" in the context of the common logarithm. Usually in math log is the common log, or base 10. But i
Re: (Score:2)
Re: (Score:2)
You don't typically measure this in seconds, you measure it in complexity. O(n), etc. The time it translates to will depend on the hardware, and usually also depends on how large the input is (ie how many nodes on the map in this case) so elapsed physical time wouldn't be a useful metric.
Place and route tools? (Score:2)
I wonder if this, or something similar is already used in place and route tools for chips and PCBs?
Re: (Score:2)
Slightly faster, in some specific cases (Score:3)
It's not clear from the article because it doesn't have hard data, but it does say this:
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.
So it is "slightly faster" than the well-known algorithm, and only in specific conditions when "you chop up the graph in the right way". The real question... is it SLOWER than Dijkstra’s in more cases to the point that on average it is actually slower?
The news here is this isn't necessarily better (the portion about the implementation being "considerably more intricate" doesn't sound great) or faster, but it is a new method to find routes.
Re: Slightly faster, in some specific cases (Score:1)
Why isn't the takeaway that an old limit has been revealed not to be a limit, just as budget constraints imagined in the 1980s have been shattered without the predicted hyperinflationary-failed-state consequences?
Re: (Score:2)
Re:Slightly faster, in some specific cases (Score:5, Insightful)
Re: (Score:2)
The implementation may be more complex, but that's exactly the kind of thing that ends up encapsulated in a library once the implementation settles down.
What they've got here sounds likely to be an intermediate step. I'm reminded of Tim Peter's series of posts when he was developing what is now known as "Timsort". The implementation combines multiple sorting algorithms (similar to how this is combining multiple shortest path algorithms), and went through many iterations as it was tuned for various different
Shall, must, should, and may, but mostly doesn't. (Score:3)
Re: (Score:2)
What's the problem with FORTRAN?
If you can read BASIC you can generally read FORTRAN, FORTRAN's lower level and cruder in places but it's similar with its concepts.
Re: (Score:2)
I don't get the the hate for FORTRAN either. Though it's worth pointing out that the algorithms in the paper [arxiv.org] are very obviously not in FORTRAN.
Re: Shall, must, should, and may, but mostly doesn (Score:5, Informative)
Aka, a heuristic like Google Maps directions (Score:2)