4 ms·

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.
  - foota 2y ago
    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 2y ago
  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 2y ago
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 2y ago
  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_Dijkstra_Maps https://roguebasin.com/?title=The_Incredible_Power_of_Dijkst...
devit 2y ago
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*.
deleted 2y ago
[deleted]
red75prime 2y ago
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 2y ago
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 2y ago
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.

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

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 2y ago
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_Dijkstra_Maps https://roguebasin.com/?title=The_Incredible_Power_of_Dijkst...

devit 2y ago

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*.

deleted 2y ago

[deleted]

red75prime 2y ago

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

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

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.