algorithm - 如何使用 Java 中的 Dijkstra 算法在方形网格中找到最短对角线路径？

Question

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

Answer 1

在 Dijkstra 算法中，我们不断选择尚未选择且与源距离最短的顶点。这里每个下一个顶点或下一个正方形都等远，距离为 1。在最小距离的正方形中，如果对角线正方形还没有包括在内，则包括它，否则选择水平横向或垂直横向正方形。从实现的角度来看，它只是使用 if..else 构造。您可以为节点的优先级维护一些字段。对角方 block 保持优先级为 1，否则为 0。

此外，Dijkstra 算法不太适合解决此问题，因为 Dijkstra 算法用于查找从单个源顶点到给定图中所有其他顶点的最短路径。尽管您没有在问题中提及，但您似乎打算找到从特定源方 block 到特定目标方 block 的最短路径。

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