How to find the shortest diagonal path in a square grid using Dijkstra's algorithm in Java?

Question

I am developing a system using Dijkstra's algorithm to display the shortest path in a square grid using Java. When a path goes diagonally, a vertical or horizontal cell is nearby, the cost of the path increases by 1. But the priority of the path must be passed through the diagonal cells. Only when there is no possible diagonal cell nearby can the path go through a vertical or horizontal cell. What is the most convenient way to do this?

Answer 1

In Dijkstra's algorithm, we continue to select vertices that have not yet been selected and that have a minimum distance from the source. Here, each next vertex or next square is equally far from a distance of one. Among the squares with the minimum distance, if the diagonal square is not already included, turn it on, otherwise select either a horizontal side or a vertical side square. From an implementation point of view , it just uses if .. else. You can save some field for node priority. Keep priority for the diagonal square and zero otherwise.

In addition, the Dijkstra algorithm is not suitable for this problem , since the Dijkstra algorithm is used to find the shortest path from one source vertex to all other vertices in a given graph. Although you have not mentioned in the question, it looks like you intend to find the shortest path from a specific source square to a specific destination area.

In addition, all reachable squares are equidistant, so there is no pleasure in using Dijkstra's algorithm. Alternatively . You can use DFS or BFS to process the grid as a graph. For another alternative, you can also take a look at the dynamic programming style of this problem, for which you can find a few examples here .