Java 如何使用 Dijkstra 算法在方格中找到最短对角线路径？
How to find the shortest diagonal path of in a squared grid using Dijkstra's algorithm in Java?
我正在开发一个使用 Dijkstra 算法的系统，以使用 Java 在方形网格中显示最短路径。当路径到达附近的对角线、垂直或水平单元格时，路径成本增加1。但路径应优先通过对角线单元格。只有当附近没有可能的对角线单元格时，路径才能通过垂直或水平单元格。最方便的方法是什么？
在 Dijkstra 算法中，我们保留 selecting 尚未 selected 且与源的距离最小的顶点。这里每个下一个顶点或下一个正方形都等远，距离为 1。在最小距离的正方形中，如果对角线正方形还没有包括在内，则包括它，否则 select 要么水平横向或垂直横向正方形。从 实现的角度来看 它只是使用 if..else 构造。您可以为节点的优先级维护一些字段。对角方块保持优先级为 1，否则为 0。
此外 Dijkstra 算法不适合解决此问题 因为 Dijkstra 算法用于查找从单个源顶点到给定图中所有其他顶点的最短路径。尽管您没有在问题中提及，但您似乎打算找到从特定源方块到特定目标方块的最短路径。
此外，所有可到达的方块都是等距的，因此在这里使用 Dijkstra'a 算法没有乐趣。 或者，您可以使用 DFS 或 BFS 将网格视为图形。对于另一种选择，您还可以查看有关此问题的动态编程风格，您可以找到一些示例 here.
我正在开发一个使用 Dijkstra 算法的系统，以使用 Java 在方形网格中显示最短路径。当路径到达附近的对角线、垂直或水平单元格时，路径成本增加1。但路径应优先通过对角线单元格。只有当附近没有可能的对角线单元格时，路径才能通过垂直或水平单元格。最方便的方法是什么？
在 Dijkstra 算法中，我们保留 selecting 尚未 selected 且与源的距离最小的顶点。这里每个下一个顶点或下一个正方形都等远，距离为 1。在最小距离的正方形中，如果对角线正方形还没有包括在内，则包括它，否则 select 要么水平横向或垂直横向正方形。从 实现的角度来看 它只是使用 if..else 构造。您可以为节点的优先级维护一些字段。对角方块保持优先级为 1，否则为 0。
此外 Dijkstra 算法不适合解决此问题 因为 Dijkstra 算法用于查找从单个源顶点到给定图中所有其他顶点的最短路径。尽管您没有在问题中提及，但您似乎打算找到从特定源方块到特定目标方块的最短路径。
此外，所有可到达的方块都是等距的，因此在这里使用 Dijkstra'a 算法没有乐趣。 或者，您可以使用 DFS 或 BFS 将网格视为图形。对于另一种选择，您还可以查看有关此问题的动态编程风格，您可以找到一些示例 here.