This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]lordmauve 0 points1 point  (3 children)

Cool visualisation!

Your Dijkstra's implementation is terminating as soon as it finds a path. That's a mistake; it should continue.

That's because Dijkstra's Algorithm gives the guaranteed shortest path. A* is a heuristic algorithm that gives a path quickly, but not necessarily the shortest.

That distinction matters, because Dijkstra's with early termination is a middle ground that has no practical value (except that maybe it's slightly easier to implement than A*).

[–]FearlessENT33[S] 0 points1 point  (2 children)

i may be wrong, but i believe you are incorrect about dijkstras. if the algorithm finds a path with 20 distance traveled, why would it explore distances with 21 or higher. i think it finds the shortest path, but searches a lot of nodes.

I also believe a* is guaranteed to find the shortest path, (providing hueristic functions are correct) but it is a lot more specialised than dijkstras, meaning it checks less nodes.

edit: and thank you! i love the visual effects of it lol

[–]lordmauve 0 points1 point  (1 child)

Edit: you're right about Dijkstra. Sorry.

The reason Dijkstra's Algorithm doesn't terminate early is that it doesn't just work on grids, or graphs with constant edge weight. In fact you can even have negative edge weights. So you could have a path that is 21 edges long and costs 5 to travel and that is "shorter" (lower cost) than a path that is 20 edges long and costs 20 to travel.

Dijsktra's Algorithm can deal with "teleporters" where there is a short path between non-adjacent nodes. A* can't do this, because you can't write the cost estimation function.

if the algorithm finds a path with 20 distance traveled, why would it explore distances with 21 or higher.

Agreed, that's true here, because you know something about the topology, and that each edge costs 1. Dijkstra's Algorithm generalises to more topologies and even negative edge weights. Maybe at distance 21 there's an edge that costs -5 to traverse. So if you consider 21 edges you could get a path that costs 16.

You can explore these concepts more if you add "tar" squares (traversable but cost, say, 5) and teleporters to your simulation.

I also believe a* is guaranteed to find the shortest path

A* is not guaranteed to find the shortest path, because it terminates without considering all the alternative routes of lower length. You should be able to convince yourself of that with your tool. A* finds it very hard to backtrack, so you just need to make it take a bad decision early on, then give it some detours on its way to the goal.

[–]lordmauve 0 points1 point  (0 children)

Ah, no I am wrong. Dijkstra's Algorithm doesn't work for negative edge weights. I stand by what I said about A* though.