任意两点间最短路问题及路径还原

考虑用动态规划的方法，只使用顶点0~k和i，j的情况下，记i到j的最短路径为d[k][i][j]。当k=0时，只考虑i和j，即d[0][i][j]=cost[i][j].然后我们就开始讨论从k到k+1是怎样变化的。

对于顶点0~k的i到j的最短路，如果这条路径不经过第k个顶点，那么d[k][i][j]=d[k-1][i][j]。当经过第k个顶点时，d[k][i][j]=d[k-1][i][k]+d[k-1][k][j](分成两短)，这样总的递推式即为d[k][i][j]=min(d[k-1][i][j]+d[k-1][i][k]+d[k-1][k][j]).

由于是三维数组，每层都要遍历所有节点，所以复杂度为o(|v|^3)。

代码如下

本文和上篇博客讨论了如何求最短路径，但未能还原出最短路径是怎么走的。

思路如下：我们需要找到满足d[j]=d[k]+cost[k][j]的顶点k，他是最短路上j前面的点，不断寻找就能找到最短路，时间复杂度为o（|e|）。

如果我们用一个数组记录这个点prev[j]=k，那么时间复杂度就变为o（|v|）。

给出dijkstra算法的代码作为参考：