如何用Dijkstra算法在Java中求出方格中最短对角路径？

Question

我正在开发一个系统，使用Dijkstra的算法来使用Java在平方网格中显示最短路径。当路径靠近对角线、垂直或水平单元时，路径成本增加1。但是路径的优先级应该是通过对角线单元。只有当附近没有可能的对角线单元格时，路径才能通过垂直或水平单元格。这样做最方便的方法是什么？

Answer 1

在Dijkstra算法中，我们不断地选择尚未被选择且距离源的距离最小的顶点。在这里，每个下一个顶点或下一个正方形的距离相等，距离为1。在距离最小的方格中，如果对角线方格尚未包括在内，则将其包括在内，否则选择水平的、横向的或垂直的侧方。从实现的角度来看，只是使用if..。否则就建造。您可以为节点的优先级维护一些字段。保持对角线正方形优先，否则为零。

此外，Dijkstra的算法并不适合于这个问题，因为Dijkstra算法用于寻找给定图中从单个源顶点到所有其他顶点的最短路径。虽然您没有在问题中提到，但看起来您希望找到从特定的源方到特定的目标方的最短路径。

而且，所有可到达的方块都是等距的，所以在这里使用Dijkstra'a算法没有什么乐趣。Alternatively，--您可以使用DFS或BFS将网格视为一个图形。对于另一种选择，您可能还可以查看有关此问题的动态编程风格，您可以找到一些示例这里。