[HN Gopher] Universal optimality of Dijkstra via beyond-worst-ca...
___________________________________________________________________
Universal optimality of Dijkstra via beyond-worst-case heaps
Author : foweltschmerz
Score : 188 points
Date : 2024-10-25 17:19 UTC (1 days 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).
| gcr wrote:
| The paper studies "... the problem of ordering vertices by
| their distance from the source vertex."
|
| If all you need is shortest path between just one pair of
| points, this result doesn't necessarily apply.
| 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.
| mlyle 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?
|
| Simple thought experiment: I have an algorithm that has path
| costs for one graph memorized and first compares to that
| graph; it's O(V+E) to compare and return the value for that
| memorized graph. It obviously beats this algorithm for that
| graph.
| foota wrote:
| Hm... technically they're saying that their algorithm
| performs as well as possible "for every single graph
| topology". Your special cased algorithm would only work for
| one particular graph in a family of isomorphic graphs
| (unless you have a linear time algorithm for the graph
| isomorphism problem, in which case please share), but would
| fail for the rest of the graphs in the family. So I think
| you could still say that their algorithm performs as well
| as possible for that topology.
| 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
| DennisL123 wrote:
| Without knowing what they actually use, I feel comfortable
| to state that the industry has moved on from Contraction
| Hierarchies to somewhat more flexible techniques. These
| allow you to take traffic information and road closures,
| and user preferences, and whatnot into account without
| requiring a full re-processing of the input data with each
| traffic update. The state of the art is a two-step
| preprocessing that first decomposes the road network into
| cells, and then processes these cells independently.
| Sometimes it goes by the name of customisable route
| planning, sometimes it is called multi-level Dijkstra.
| ahoka wrote:
| One trick we used when I was in the transportation business
| is to pre-calculate the distances between border crossings
| and gas stations.
| DennisL123 wrote:
| Storing the distances for all pairs is prohibitively
| expensive. Also, you'd need to store the path information as
| well. Fortunately, road networks exhibit a lot of
| hierarchical structure. For example, when going far away, you
| will almost certainly use the long-distance sub-network, i.e.
| highways. It is possible to exploit this in a preprocessing
| step that adds a linear amount of information, which is in
| turn used to speed up queries.
| bee_rider wrote:
| TDH seems like it would tend to coincidentally reproduce the
| tendency of animals (humans included) to create paths by having
| lots of people travel through somewhere. The cause and effect
| is flipped, but the player doesn't have to know that, right?
| foota wrote:
| TDH doesn't actually change the paths used, it only makes
| determining them more efficient. There's different names for
| this family of related techniques. There's an unfinished
| article (not mine) talking more about this here: https://www.
| redblobgames.com/pathfinding/heuristics/differen...
| telgareith wrote:
| FYI, TDH sounds like what Skyrim or one of the previous games
| uses.
|
| I can't remeber exactly, but $thing was supposed to be hard to
| find, but because of how they baked in pathing costs- if you
| followed something it'd lead you there.
| foota wrote:
| I think this is what you're referring to:
| https://twitter.com/JoelBurgess/status/1428008041887281157
|
| Some discussion here:
| https://news.ycombinator.com/item?id=28230305, but half of it
| is complaints about twitter.
| 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).
| akoboldfrying wrote:
| A sibling post answers your question, but I found your quote
| interesting for a different reason: This working set property
| seems like something that would be very useful in practice for
| quite a few problems, even if it can't be pushed all the way to
| proving universal optimality. We often have some freedom in
| choosing what order to supply inputs to a problem we're trying
| to solve; if we can order things so that, 99% of the time, the
| minimum item that we're looking for turns out to be within the
| last 1000 items considered instead of the complete set of
| 1000000, that's a nearly 10x constant factor speed up right
| there.
| zeroonetwothree wrote:
| Well not exactly because it's the log of the number. So it's
| log 1000 vs log 1000000 which is a much smaller difference.
|
| Also if you actually know the minimum item it's much better
| for it to be first because it means you can skip almost all
| the work. The paper is focused on doing the best for a worst
| case input. In real life if you can guess you can improve the
| average case substantially. For example, this is what A*
| tries to do.
| noctune wrote:
| You can use a radix heap rather than a binary heap. I have an
| implementation here, with benchmarks using pathfinding:
| https://github.com/mpdn/radix-heap
|
| It has the nice property that the amortized cost of
| pushing/popping an element is independent of the number of
| other elements in the heap.
| akoboldfrying wrote:
| Robert Tarjan's name is on a simply astounding number of
| breakthrough papers in graph algorithms, spanning decades.
| joshhug wrote:
| I had him as a teaching assistant when I was teaching data
| structures at Princeton back in Fall 2013. Princeton CS has
| their professors rotate through as TAs every so often through
| their courses.
|
| That semester, I made a slight mistake on the final exam where
| I asked students to create an algorithm that could find the
| second shortest path from s to every other vertex in a graph. I
| forgot to specify that the second shortest path should be
| simple (i.e. should not reuse any vertex twice). Having to deal
| with non-simple paths makes the problem much much harder.
|
| None of the students figured it out in the time available, and
| I'm sure I would also have been stumped if I had tried to solve
| the problem. Bob figured it out though. And then I remember he
| graded all 150 solutions to the problem himself, having as a
| blast as he went through students attempts at an effectively
| impossible problem.
___________________________________________________________________
(page generated 2024-10-26 23:04 UTC)