Hacker News Reader

Comment by jvanderbot | Hacker News Reader

> Dijkstra's algorithm is a general one, That can be used in any case,

I take issue with this statement. "any case" implies it's more general than A star, which is not true, it's a specialization of A star with (ok you win) h(v) set to nothing. It necessarily cannot solve as many problems as a star.

And Dijkstra's won't work in "any case" at all, esp graphs with negative edge weights.

The explanation struck me as glossing over too much, to the point of being misleading. Perhaps I'm being too pedantic, fine, but a more enlightened comparison would read more like our discussion than what was given.

View on HN

> It necessarily cannot solve as many problems as a star.

Could you give an example of a positive-weight shortest path problem with A* can solve, but Dijkstra's algorithm cannot? I do not believe there is such a thing. Or did you mean something else?

> And Dijkstra's won't work in "any case" at all, esp graphs with negative edge weights.

A* won't solve those either.

i would rather say that a* is an optimization of dijkstra's algorithm

they both solve the single-pair shortest-path problem in digraphs with nonnegative arc weights

a* which explores nodes in a different, better order thank dijkstra's algorithm, but can only be applied in cases where you can compute an admissible heuristic

that makes it less general than dijkstra's algorithm, which works to find shortest paths in any digraph with nonnegative arc weights, not just the ones where an admissible heuristic can be computed

any problem you can solve with a* can be solved with dijkstra's algorithm (usually more slowly) but the converse is not true

now, in a sense, a* with an inadmissible heuristic such as h(v)≡0 is 'more general' in the sense that it can emulate dijkstra's algorithm and also do other things; you could say that a* is a class of algorithms of which dijkstra's algorithm is one

You realize it had the constraints of a poem, and needed to take some liberty with description there?

Sure sure. I'm being pedantic. But replacing two sentences would fix it.

Reply on news.ycombinator.com