[HN Gopher] Universal optimality of Dijkstra via beyond-worst-ca...
___________________________________________________________________
Universal optimality of Dijkstra via beyond-worst-case heaps
Author : foweltschmerz
Score : 112 points
Date : 2024-10-25 17:19 UTC (5 hours ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| blt wrote:
| The paper's name is shorter than this post title, and summarizes
| the result much better.
| mikestew wrote:
| 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.
| westurner wrote:
| "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
| impure wrote:
| A* has entered the chat
| twojacobtwo wrote:
| Several other commenters have now pointed out the
| differentiations, in case you weren't aware.
| fiddlerwoaroof wrote:
| Does this mean that Dijkstra's algorithm can perform better than
| something like A*?
| entropicdrifter wrote:
| There's a notable exception:
|
| >when combined with a sufficiently efficient heap data
| structure
|
| So it depends on the circumstances a bit.
| jprete wrote:
| 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.
| foota wrote:
| 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.
| jvanderbot wrote:
| A* is not solving a different problem. What happens if h(x)=0
| for all x in A*?
| Jtsummers wrote:
| > 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 wrote:
| 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.
| superjan wrote:
| 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.
| Jtsummers wrote:
| 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 path _s_ 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 wrote:
| 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 wrote:
| 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*.
| red75prime wrote:
| 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.
| mvkg wrote:
| The paper's claim for Dijkstra's is it's "a single algorithm
| performs as well as possible for every single graph topology".
| A* is an augmented version of Dijkstra's only applicable when
| there is a priori knowledge of a good heuristic for the
| topology (e.g. manhattan distance in a cartesian plane). Since
| there is almost certainly no heuristic that is universally
| optimal for all topologies, A* shouldn't be more universally
| optimal than Dijkstra's (and can probably perform worse given a
| bad heuristic).
| moron4hire wrote:
| 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.
| o11c wrote:
| That's wrong, A* can trivially handle a set of points at one
| end (you might have to "reverse" the direction depending on
| which end has the set).
| foota wrote:
| 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.
| kevinwang wrote:
| > 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.
| foota wrote:
| No, I don't believe so.
|
| It clarifies specifically what problem it is optimal for "We
| prove that our working-set property is sufficient to
| guarantee universal optimality, specifically, for the problem
| of ordering vertices by their distance from the source
| vertex", but A* only explores a subset of vertices based on
| the heuristic, so it can be more efficient.
| Jadrago wrote:
| Does google maps use something like this? I imagine all pairs
| is too expensive, but the topology should be fairly consistent
| over time
| urbandw311er wrote:
| Google maps uses something called contraction hierarchies
| m0llusk wrote:
| 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.
| heraldgeezer wrote:
| I recognize the name due to studying CCNA in the past. His name
| comes up with OSPF routing protocol.
| vanderZwan wrote:
| > _Our universal optimality result reveals a surprisingly clean
| interplay between this property and Dijkstra's algorithm: Any
| heap with the working set property enables the algorithm to
| efficiently leverage every structural attribute of the graph it
| operates on, to the fullest extent that any comparison-based
| algorithm possibly can._
|
| That last bit makes me wonder: what would a shortest path
| algorithm _without_ comparisons look like? Are there also "radix
| sort" like approaches to shortest-path algorithms that surpass
| comparison-based algorithms or something?
| Sesse__ wrote:
| Yes. If your distances are dense integers, you can use a simple
| array as the priority queue in Dijkstra, and it will be faster
| than a heap (Dial's algorithm).
___________________________________________________________________
(page generated 2024-10-25 23:00 UTC)