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.