第一列到第n列的最短路径（两列之间的距离为差值的绝对值，例如11与14的最短距离为4，11与10的最短距离为1）

|(11 - 14 )| = 4？
|(11 - 10 | = 1;

楼主真的很抱歉不知道您在说什么。。 算第一列到第N列到最短路径？？ 不能直接算嘛

相临两列之间的最短路径加起来不就是1-n的最短路径之一吗，贪婪算法？

假如 三条路的长度为 x,y,z 假如单纯的通过foreach循环可能造成复杂度为f(xy) + f(yz)

所以如和去做才能减少复杂度
第一假如我x 走 y
假设我们为两条路xy进行排序(小到大排序) 我从 x 的最小值(键值0)11开始走起,最近的可能是y的最小值10(键值0)做判断,假设y的值大于x的话,那么x10到y的最小路径就只有y0.假如比x10要小,那么我们继续往y的下一个键值判断y[1],直到找到比x10要大的数(假设为y[y3]),从中判断到底是y[y3]小,还是yy3-1.从中找到最小路径,假设找到0时候可以直接跳出循环

或者换一种思维,把所有的列的数据放到一个二维数轴,以第一列的数据作为原点,路线向两边扩散,只要哪个最短的线能连接所有列的数据,那么那路径应该是最短的

做好二位数轴之后,一眼看就知道
15,18,17
15,14,17
两种都是路径最短

此题如果穷举所有n₁ n₂ n₃ ... （n_k是每列的大小）条路径，n行n列的话复杂度就是O(nⁿ)。下面借助有向图最短路径算法可将复杂度降为O(n⁴)。

• 把给定矩阵中每个元素的位置作为节点，相邻两列节点之间的“距离”作为边的权重，构建有向图。这一步的复杂度为

$$O(n_1 n_2 + n_2 n_3 + \cdots + n_{n-1}n_n)=O(n^3)$$

• 问题转化为求解有向图的最短路径。Dijkstra算法可计算单节点源到其它所有节点的最短路径，复杂度为O(E + V log V)，其中E和V分别是图的边数和节点数。在本问题中，E=O(n³)，V=O(n²)。我们需要计算以第一列所有节点为源的到最后一列所有节点的最短路径。这一步的复杂度就是：

$$n\ O(E+V\log{V})=n\ O(n^3+n^2\log{n^2})=O(n^4)$$

• 最后需要选择n个结果中最好的一个，复杂度为O(n)。

综上可知总复杂度为O(n⁴)。