New Method Is the Fastest Way To Find the Best Routes (quantamagazine.org)
- Reference: 0178615188
- News link: https://science.slashdot.org/story/25/08/08/1550231/new-method-is-the-fastest-way-to-find-the-best-routes
- Source link: https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/
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.
[1] https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/
Travelling salesmen (Score:2)
will benefit from this research!
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:2)
There is a new salesman born every minute.
Re: (Score:2)
He's making a reference to "Death of a Salesman"
Re: (Score:2)
And I to P.T. Barnum.
Re: (Score:2)
> no I heard he's dead.
No, he's just resting; all shagged out from a long trip.
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)
There's the brute-force solution.
Re: (Score:3)
Actually, there is a formal analytical solution. It's just not polynomial. You can list all possible ways, which is O(n!), and then take the shortest one.
Re: (Score:2)
(It's similar to other famous problems like Squaring the Circle. Yes, there is a solution, but it's not algebraic, as pi is non-algebraic.)
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)
It's the same with the Traveling Salesman. Right now, there is no polynomial solution known, so it is not in P. On the other hand, a non-deterministic automaton can find the shortest path in polynomial time, hence it is in NP. If we could find a solution in polynomial time for a deterministic automaton, we would have proof for P=NP.
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.
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)
AI uses a LOT more power than route optimization does!
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:2)
The algorithm is for a network of paths with arbitrary, i.e. unitless weights. It's not just for making your Google Maps journey faster!
Re:How much faster? (Score:5, Informative)
O(e*log^2/3 v) for the new one, and O(e + v*log v) for the old one (where e is edge and v is vertex).
Re: (Score:2)
The new algorithm is obviously only faster for a subset of shortest path problems. It's not always faster, only when there aren't many edges. My math isn't good enough to figure out for what values of e and v it is faster.
Re:How much faster? (Score:5, Informative)
I figured it out, when there are (roughly) more than e*log(e) edges for each vertex, then the new algorithm is faster. So for a graph with 3 vertices, anything with more than five edges goes faster with Dijkstra's (the old algorithm).
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)
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)
Optimum is the keyword. P&R settles for less than optimum to achieve results in reasonable times. The revolutions in P&R tend to be faster while still achieving good results.
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:2)
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)
To go from computer science algorithm big O complexity analysis to (American?) politics and economics has gotta be a troll, right? Like so many Slashdot (and other internet) conversions are perpetually derailed onto irrelevant topics.
Re:Slightly faster, in some specific cases (Score:4, Insightful)
It seems like it might perform worse in cases where the graph's vertices are maximally connected to each other (basically a transitive closure) and the number of edges is effectively the square of the number of vertices. Then you have O(v^2 * log^2/3 v) vs. O(v^2 + v log v). I don't think that's too common though.
Shall, must, should, and may, but mostly doesn't. (Score:3)
I look forward to 25 years of small and open-source players just using Bellman-Ford and Dijkstra instead because the RFC for this algorithm is unreadably opaque and the reference implementation is in FORTRAN.
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 [1]the paper [arxiv.org] are very obviously not in FORTRAN.
[1] https://arxiv.org/pdf/2504.17033
Re: Shall, must, should, and may, but mostly doesn (Score:4, Informative)
That's not FORTRAN, that's CS paper pseudocode. There's an [1]independent C++ implementation here. [github.com]
[1] https://github.com/Suigin-PolarisAi/BMSSP
Aka, a heuristic like Google Maps directions (Score:2)
Not a precisely perfect minimum cost, but an almost solution that's cheaper. Congrats they've found another method.
This is my jam! (Score:1)
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)
we can be friends!
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: (Score:2)
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":
[1]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.
[1] https://deepmind.google/discover/blog/alphaevolve-a-gemini-powered-coding-agent-for-designing-advanced-algorithms/