使用单源最短路径遍历棋盘
Using Single Source Shortest Path to traverse a chess board
假设我们有一个 n x n 的棋盘（或者换句话说是一个矩阵），每个方块都有一个权重。一块可以水平或垂直移动，但不能沿对角线移动。每次移动的成本将等于棋盘上两个方格的差异。使用算法，我想找到单个棋子从正方形（1,1）移动到正方形（n，n）的最小成本，它在多项式时间内具有最坏情况的时间复杂度。
dikstras算法可以解决这个问题吗？我下面的算法能解决这个问题吗？ Diijkstras 在多项式时间内已经可以是 运行，但是是什么让它成为这个时间复杂度呢？
伪代码：
我们有一些空集S，一些整数V，并输入一个未加权的图。之后，我们完成了一个邻接矩阵，显示了没有无穷大加权顶点的边的成本，虽然矩阵没有选择所有顶点，但我们找到了一个顶点，如果平方值小于我们当前所在的正方形，则移动到那个正方形并用两个正方形之间的差异更新 V 并更新 S 标记每个已访问的顶点。我们执行此过程，直到没有更多的顶点。
谢谢。
由于您正在尝试寻找最小成本路径，因此您可以使用 Dijkstra 的方法。由于 Dijkstra 在最坏的情况下是 O(|E| + |V|log|V|)，其中 E 是边数，V 是图中的顶点数，这满足您的多项式时间复杂度要求。
但是，如果您的算法只考虑与移动的开始和结束方块相关的成本，而不考虑中间节点，那么您必须将所有可能的开始和结束方块连接在一起，以便您可以 "short-cuts" 围绕中间节点。
假设我们有一个 n x n 的棋盘（或者换句话说是一个矩阵），每个方块都有一个权重。一块可以水平或垂直移动，但不能沿对角线移动。每次移动的成本将等于棋盘上两个方格的差异。使用算法，我想找到单个棋子从正方形（1,1）移动到正方形（n，n）的最小成本，它在多项式时间内具有最坏情况的时间复杂度。
dikstras算法可以解决这个问题吗？我下面的算法能解决这个问题吗？ Diijkstras 在多项式时间内已经可以是 运行，但是是什么让它成为这个时间复杂度呢？
伪代码：
我们有一些空集S，一些整数V，并输入一个未加权的图。之后，我们完成了一个邻接矩阵，显示了没有无穷大加权顶点的边的成本，虽然矩阵没有选择所有顶点，但我们找到了一个顶点，如果平方值小于我们当前所在的正方形，则移动到那个正方形并用两个正方形之间的差异更新 V 并更新 S 标记每个已访问的顶点。我们执行此过程，直到没有更多的顶点。
谢谢。
由于您正在尝试寻找最小成本路径，因此您可以使用 Dijkstra 的方法。由于 Dijkstra 在最坏的情况下是 O(|E| + |V|log|V|)，其中 E 是边数，V 是图中的顶点数，这满足您的多项式时间复杂度要求。
但是，如果您的算法只考虑与移动的开始和结束方块相关的成本，而不考虑中间节点，那么您必须将所有可能的开始和结束方块连接在一起，以便您可以 "short-cuts" 围绕中间节点。