c++ - 最短路径加权矩阵

Question

找到从给定 n x n 矩阵最左边的任何元素到矩阵最右边的任何元素的最短路径。

移动:一次只能移动一格。您可以向左、向右、左上、右上、左下和右下移动。

权重:矩阵上从X元素移动到Y的代价是|Y - X|

运行时:设计的算法必须至多为 O(n²)

示例:

到目前为止尝试过:

这个解决方案有问题。

运行时间为 O(n² Log n²)，比 O(n²) 慢。

Answer 1

当您考虑图形中的边是有向的时，您可以利用这一点，您的图形是非循环的并且具有(部分)拓扑顺序。在这种情况下，您可以只计算每个节点从左到右的距离，即 column bei column。

在第一列中，所有节点的距离为0，即d(左上)=0，d(左中)=0，d(左下)=0。

在第二列(以及所有后续列)中，您最多可以从三个候选值中选择最小值，例如 d(Upper middle)=MIN[d(Upper left)+4,d(middle left) )+2]=2.

也就是说，从左到右计算每个节点的值只需要恒定的时间，总的来说是 Theta(n^2)。更一般地，对于 N 个节点和 M 个边，这需要 O(NM) 来进行单源最短路径计算。

[编辑:我删除了对动态规划的引用，因为它带来的困惑多于帮助。添加了示例。]