Dijkstra's algorithm prove as universally optimal way to find graph's best route
22 comments
·October 25, 2024foota
kevinwang
> When you have some knowledge of the topology of the graph you can use different techniques to do better than djikstra's.
But that statement doesn't apply to the version of Dijkstra's developed in this paper right?
> Universal optimality is a powerful beyond-worst-case performance guarantee for graph algorithms that informally states that a single algorithm performs as well as possible for every single graph topology.
blt
The paper's name is shorter than this post title, and summarizes the result much better.
mikestew
It took me a few minutes before I realized that putting “n” at the end of “prove” makes the HN title readable.
But yeah, should have just used the original title.
m0llusk
In most real situations a graph is likely to be a model with some expected characteristics or perhaps data regarding real situations. Either way with modern computing it seems like in many cases using machine learning to predict the path or next steps on the path might actually end up being a more optimal method. The issue is how much data and modeling is available and how any processing of that would best be accounted for in final results that make use of any analysis.
fiddlerwoaroof
Does this mean that Dijkstra’s algorithm can perform better than something like A*?
Jtsummers
The two algorithms solve different (but related) problems. A* finds the shortest path from a source to a single target node. Dijkstra's finds the shortest paths from a source to all other nodes. If you're using Dijkstra's as a search algorithm then it may be slower than A* (often will be, but it depends on the heuristic), but you'll be terminating the algorithm early (once your target has been found you don't need to continue the algorithm).
The algorithm under discussion is not that search-use of Dijkstra's, but the original all shortest paths use, so it's not directly comparable here to A*.
fiddlerwoaroof
Ok, this makes sense, it’s been a while since I did a deep dive into these algorithms for a roguelike project.
This article I found really interesting at the time: https://roguebasin.com/?title=The_Incredible_Power_of_Dijkst...
devit
A* with a consistent heuristic is Dijkstra on a modified graph whose edge weights are the original edge weights plus f(target) - f(source) where f is the A* "heuristic".
If the heuristic is not consistent, the edge weights aren't necessarily nonnegative, but you can still use the "hybrid Bellman–Ford–Dijkstra algorithm", which is a generalization of Dijkstra that works for all graphs, and should be asymptotically better than naive A*.
jprete
A* is faster in practice if the heuristics used by the specific implementation are accurate and if the graph is "general" for the problem space. I'm being very loose with the word "general" but essentially it should have typical structure for the problem space it represents.
There's almost certainly a paper somewhere proving that A* with a given heuristic can always be made O(large) by choosing the right adversarial inputs.
red75prime
Others pointed that A* and Dijkstra's algorithm solve different problems. But there's another possibility: less general but more efficient algorithm. For example, there are faster algorithms for planar graphs.
null
foota
I think A* is solving a different problem than dijkstra's, since it requires an admissible heuristic to do any better than dijkstra's.
As long as you have an admissible heurustic, A* won't ever perform worse than dijkstra's.
superjan
An example for those not in the know: to find a shortest route on a realworld map, an admissible heuristic would be that the minimum travel distance between two nodes will be a straight line. While examining options, A* takes this into account, Dijkstra does not.
jvanderbot
A* is not solving a different problem. What happens if h(x)=0 for all x in A*?
Jtsummers
> A* is not solving a different problem.
A* finds the shortest path from a node to a single other node. Dijkstra's finds the shortest paths from a node to all other nodes. If you use it as a search algorithm to find the shortest path to a single target, then yes, it's equivalent to A* with h(x)=0, but you're terminating Dijkstra's early (once your target is found) and not running the full algorithm.
foota
A different problem in the sense that A* is useless (it degrades to dijkstra's) when there is no admissible heuristic. So I think it's reasonable to say that A* solves a different problem (namely, path finding when there is an admissible heuristic), since when there's no admissible heuristic it is identical to dijkstra's.
entropicdrifter
There's a notable exception:
>when combined with a sufficiently efficient heap data structure
So it depends on the circumstances a bit.
westurner
"Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps" (2024) https://arxiv.org/abs/2311.11793 :
> Abstract: This paper proves that Dijkstra's shortest-path algorithm is universally optimal in both its running time and number of comparisons when combined with a sufficiently efficient heap data structure.
Dijkstra's algorithm: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
NetworkX docs > Reference > Algorithms > Shortest Paths: https://networkx.org/documentation/stable/reference/algorith...
networkX.algorithms.shortest_path.dijkstra_path: https://networkx.org/documentation/stable/reference/algorith... https://github.com/networkx/networkx/blob/main/networkx/algo...
/? Dijkstra manim: https://www.google.com/search?q=dijkstra%20manim
moron4hire
This came up for me not long ago. A* is a specialization of Dijkstra's that is the canonical "path finding algorithm" for game development. A* is good for finding how to get from a specific point A to a specific point B. But I wanted to know how to get from any point A to a list of point Bs. And so it turned out that the extra work that Dijkstra's does that A* skips is exactly the work you want when doing such a thing. It's also cacheable, which is incredible in the modern era of having basically infinite memory for this sort of thing.
impure
A* has entered the chat
twojacobtwo
Several other commenters have now pointed out the differentiations, in case you weren't aware.
I've gone down a bit of a rabbit hole on path finding in the last week or two (most recently, this isn't the first time). When you have some knowledge of the topology of the graph you can use different techniques to do better than djikstra's.
Of course, if you have lots of time and space and a completely static graph, you can run all pairs shortest paths and simply store all the results for O(1) path lookup, but there are intermediates for varying types of graphs. This stack exchange article is a good overview: https://cstheory.stackexchange.com/questions/11855/how-do-th....
I've been wondering about how well D* lite would perform in practice with a somewhat varying graph. I read some suggestions that if the graph is changing even a bit on occasion, then it will mostly degrade to A*, since many changed paths would need to be re-evaluated.
In the context of games, I've also been thinking about a technique called true distance heurustics (TDH), where you essentially precompute the distances between some fixed set of nodes, and then use those as a part of the heurustic for A* (or D* lite in this case), but it seems like updating these TDH in the case of a changing graph might introduce just as much overhead as not having them in the first place. It might be an interesting trade off though, if you have some "lines" (e.g., think train lines) that are much faster than roadways, you could handle each of these specially via the TDH, and in exchange you would be able to assume a lower "max speed" for use with the A* heurustic, allowing you to explore fewer paths (since with a lower "max speed" paths will more rapidly increase in cost), whereas if you had to assume all car based paths could move as fast as a train, you would have to explore more paths.