5 ms·

Universal optimality of Dijkstra via beyond-worst-case heaps

203 points by foweltschmerz 2y ago

blt 2y ago
The paper's name is shorter than this post title, and summarizes the result much better.
- mikestew 2y ago
  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 2y ago
"Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps" (2024) https://arxiv.org/abs/2311.11793 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 https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm NetworkX docs > Reference > Algorithms > Shortest Paths: https://networkx.org/documentation/stable/reference/algorithms/shortest_paths.html https://networkx.org/documentation/stable/reference/algorith... networkX.algorithms.shortest_path.dijkstra_path: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.dijkstra_path.html https://networkx.org/documentation/stable/reference/algorith... https://github.com/networkx/networkx/blob/main/networkx/algorithms/shortest_paths/weighted.py https://github.com/networkx/networkx/blob/main/networkx/algo... /? Dijkstra manim: https://www.google.com/search?q=dijkstra%20manim https://www.google.com/search?q=dijkstra%20manim
impure 2y ago
A* has entered the chat
- twojacobtwo 2y ago
  Several other commenters have now pointed out the differentiations, in case you weren't aware.
fiddlerwoaroof 2y ago
Does this mean that Dijkstra’s algorithm can perform better than something like A*?
- entropicdrifter 2y ago
  There's a notable exception: >when combined with a sufficiently efficient heap data structure So it depends on the circumstances a bit.
- jprete 2y ago
  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 2y ago
  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 2y ago
    A* is not solving a different problem. What happens if h(x)=0 for all x in A*?
    - Jtsummers 2y ago
      > 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.
moron4hire 2y ago
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 2y ago
  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 2y ago
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-the-state-of-the-art-pathfinding-algorithms-for-changing-graphs-d-d-l 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 2y ago
  > 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 2y ago
    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.
m0llusk 2y ago
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 2y ago
I recognize the name due to studying CCNA in the past. His name comes up with OSPF routing protocol.
vanderZwan 2y ago
> 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__ 2y ago
  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 2y ago
  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 2y ago
    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.
    - 2y ago
akoboldfrying 2y ago
Robert Tarjan's name is on a simply astounding number of breakthrough papers in graph algorithms, spanning decades.
- joshhug 2y ago
  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.
  - UltraSane 2y ago
    Being that damn smart must feel amazing, almost like having a superpower.
vtodekl 2y ago
[dead]

203 points by foweltschmerz 2y ago

blt 2y ago

The paper's name is shorter than this post title, and summarizes the result much better.

mikestew 2y ago
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 2y ago

"Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps" (2024) https://arxiv.org/abs/2311.11793 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 https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm NetworkX docs > Reference > Algorithms > Shortest Paths: https://networkx.org/documentation/stable/reference/algorithms/shortest_paths.html https://networkx.org/documentation/stable/reference/algorith... networkX.algorithms.shortest_path.dijkstra_path: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.weighted.dijkstra_path.html https://networkx.org/documentation/stable/reference/algorith... https://github.com/networkx/networkx/blob/main/networkx/algorithms/shortest_paths/weighted.py https://github.com/networkx/networkx/blob/main/networkx/algo... /? Dijkstra manim: https://www.google.com/search?q=dijkstra%20manim https://www.google.com/search?q=dijkstra%20manim

impure 2y ago

A* has entered the chat

twojacobtwo 2y ago
Several other commenters have now pointed out the differentiations, in case you weren't aware.

fiddlerwoaroof 2y ago

Does this mean that Dijkstra’s algorithm can perform better than something like A*?

entropicdrifter 2y ago
There's a notable exception: >when combined with a sufficiently efficient heap data structure So it depends on the circumstances a bit.
jprete 2y ago
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 2y ago
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 2y ago
  A* is not solving a different problem. What happens if h(x)=0 for all x in A*?
  - Jtsummers 2y ago
    > 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.

moron4hire 2y ago

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 2y ago
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 2y ago

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-the-state-of-the-art-pathfinding-algorithms-for-changing-graphs-d-d-l 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 2y ago
> 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 2y ago
  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.

m0llusk 2y ago

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 2y ago

I recognize the name due to studying CCNA in the past. His name comes up with OSPF routing protocol.

vanderZwan 2y ago

> 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__ 2y ago
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 2y ago
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 2y ago
  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.
  - 2y ago

akoboldfrying 2y ago

Robert Tarjan's name is on a simply astounding number of breakthrough papers in graph algorithms, spanning decades.

joshhug 2y ago
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.
- UltraSane 2y ago
  Being that damn smart must feel amazing, almost like having a superpower.

vtodekl 2y ago

[dead]