动态规划-最短路径问题.docx

最短路径问题
下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。
｛求城市who与城市E的最短距离｝
｛找到目标城市｝
｛初始化最短路径为最大｝
S｛未访问｝
｛置访问标最短路径问题
下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。
｛求城市who与城市E的最短距离｝
｛找到目标城市｝
｛初始化最短路径为最大｝
S｛未访问｝
｛置访问标志｝
｛累加城市E至城市Who的路径长度｝
｛回溯后，恢复城市i未访问状态｝
｛如果最短则记下｝
｛返回最短路径长度｝
｛计算最短路径长度｝
j；
现在，我们想从城市a到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？设
DiS[x]为城市x到城市E的最短路径长度(x表示任意一个城市)；
map[i,j]表示i,j两个城市间的距离，若map[i，j]=0,则两个城市不通；
我们可以使用回溯法来计算DiS[x]：var
S：未访问的城市集合；
functionsearch(who{x})：integer；
begin
ifWho=EThenSearch〜0
Elsebegin
min~maxint；
fori取遍所有城市Doif(map[Who，i]>0{有路})and(ithenbegin
S-S—[i]；
j~map[Who,i]+search(i)；S-S+[i]；ifjVminThenmin~end；{then}search~min；End；{else}
End；{search}
begin
S-除E外的所有城市；
Dis[a]^search(a)；
输出Dis[a]；
end.{main}
这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间复杂度为O(n!)，这是一个“指数级”的算法。那么，还有没有效率更高的解题方法呢？
首先，我们来观察上述算法。在求bl到E的最短路径的时候，先求出从C2到E的最短路径；而在求从b2刭E的最短路径的时候，又求了一遍从C2刭E的最短路径。也就是说，从C2到E的最短路径求了两遍。同样可以发现，在求从Cl、C2刭E的最短路径的过程中，从Dl到E的最短路径也被求了两遍。而在整个程序中，从Dl到E的最短路径被求了四遍，这是多么大的一个浪费啊！如果在求解的过程中，同时将求得的最短路径的距离“记录在案”，以便将来随时调用，则可以避免这种重复计算。至此，一个新的思路产生了，即
由后往前依次推出每个Dis值，直到推出Dis「a」为止。
问题是，究竟什么是“由后往前”呢？所谓前后关系是指对于任意一对城市i和j来说，如果满足“或者城市i和城市j不连通或者dis[i]+map[i,j]三dis[j]”的条件，则定义为城市i在前、城市j在后。因为如果城市i和城市j连通且Dis[i]+map[i，j]<Dis「j」，则说明城市j至城市E的最短路径长度应该比Dis[j]更优。可城市j位于城市i后不可能推出此情况，以至于影响最后的解。那么，我们应该如何划分先后次序呢？
阶段0阶段】阶段7阶段3阶萇4
如上图所示，从城市a出发，按照与城市a的路径长度划分阶