Skip to main content

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

4
  • 2
    Suppose you are trying to find directions from point A to B, the optimal distance for which is d. Dijkstra's algorithm will, at the very least, examine all points at distance at most d from A. If A is San Francisco and B is Boston, this means it examines most of the US. N'est-ce pas?
    – A. Rex
    Commented Jan 10, 2009 at 1:04
  • 2
    Yes, it is. What I wanted to get at is that A* can be used instead and that it always finds an optimal solution (even though it uses a heuristic)!
    – Konrad Rudolph
    Commented Jan 10, 2009 at 10:43
  • Yes, of course. After I wrote my original post, I thought about the word "heuristic" that I used. It's a bit inaccurate here, because it does find an optimal solution.
    – A. Rex
    Commented Jan 10, 2009 at 15:52
  • 2
    Well, the point is that A* uses a heuristic (as opposed to being one) to determine the next step. This one decision can indeed be suboptimal. But it only affects runtime, not the result, since it only determines how much better than Dijstra it guesses.
    – Konrad Rudolph
    Commented Jan 10, 2009 at 20:28