Dijkstra Algorithm with Chebyshev Distance

Question

I have been using Dijkstra Algorithm to find the shortest path in the Graph API which is given by the Princeton University Algorithm Part 2, and I have figured out how to find the path with Chebyshev Distance.

Even though Chebyshev can move to any side of the node with the cost of only 1, there is no impact on the Total Cost, but according to the graph, the red circle, why does the path finding line moves zigzag without moving straight?

Will the same thing will repeat if I use A* Algorithm?

Answer 1

If you want to prioritize "straight lines" you should take the direction of previous step into account. One possible way is to create a graph G'(V', E') where V' consists of all neighbour pairs of vertices. For example, vertex v = (v_prev, v_cur) would define a vertex in the path where v_cur is the last vertex of the path and v_prev is the previous vertex. Then on "updating distances" step of the shortest path algorithm you could choose the best distance with the best (non-changing) direction.

Also we can add additional property to the distance equal to the number of changing a direction and find the minimal distance way with minimal number of direction changes.

Answer 2

It shouldn't be straight in particular, according to Dijkstra or A*, as you say it has no impact on the total cost. I'll assume, by the way, that you want to prevent useless zig-zagging in particular, and have no particular preference in general for a move that goes in the same direction as the previous move.

Dijkstra and A* do not have a built-in dislike for "weird paths", they only explicitly care about the cost, implicitly that means they also care about how you handle equal costs. There are a couple of things you can do about that:

1. Use tie-breaking to make them prefer straight moves whenever two nodes have equal cost (G or F, depending on whether you're doing Dijkstra or A*). This gives some trouble around obstacles because two choices that eventually lead to equal-length paths do not necessarily have the same F score, so they might not get tie-broken. It'll never give you a sub-optimal path though.
2. Slightly increase your diagonal cost, it doesn't have to be a whole lot, say 10 for straight and 11 for diagonal. This will just avoid any diagonal move that isn't a shortcut. But obviously: if that doesn't match the actual cost, you can now find sub-optimal paths. The bigger the cost difference, the more that will happen. In practice it's relatively rare, and paths have to be long enough (accumulating enough cost-difference that it becomes worth an entire extra move) before it happens.