在求两点之间的最短路径时，有一种比较优秀的方法：“Floyd-Warshall”算法，其算法的中心思想是这样的：
求A至B的满足中间结点不超过K的最短路径。而后，随着K逐渐增加至N而求出A至B的最短路径。则其算法的结构如下：
For K=1 To N {K从1增至N}
For A=1 To N Do
For B=1 To N Do {求每一对结点的中间结点不超过K的最短路径}
IF (Map[A,K]>0) And (Map [K,B]>0) Then
{如果A与K，K与B均可达}
IF (Map[A,B]=0) Or (Map[A,B]>Map[A,K]+Map[K,B]) Then
{如果A、B不可达，或者A、B之间的路径不如A-K-B这条路径短，则改变Map[A,B]的值}
Map[A,B]:=Map[A,K]+Map[K,B];
这个问题在确定K是与Floyd算法相同，所以这个问题实质上是一个“双重动态规划”问题。具体算法如下：
For G:=1 To M Do {分M个阶段来解这个问题}
For K:=1 To N Do
For I:=1 To N Do
For J:=1 To N Do
{Floyd算法}
Begin
For T:=0 To G Do
If Map[I,K,T]+Map[K,J,G-T]<Map[I,J,G] Then
Map[I,J,G]:=Map[I,K,T]+Map[K,J,G-T];
End;
说明：这个问题的Map数组的初始值与上一个Floyd算法不一样，初始值均为MaxInt。
这个算法的时间复杂度为O(N^3*M^2)，约为O(N^5)，还是一个多项式级的算法。
总结
这个问题虽然借助图的模型，但实质上是一个“动态规划”的问题。这个题目主要的意义在于：图论中的很多算法都是有它自己的背景的，我们应该深入考虑算法的根本所在。Floyd算法的实质思想就是“动态规划”，它虽然在图论中呈现出巨大的作用，但其“动态规划”的结构、原理还是应该“独立而论”的。本题就是深入挖掘了Floyd算法的“动态规划”原理，并在其基础上提出的“双重动态规划”问题。 作者: admin 时间: 2018-4-16 12:03
TOP1 WWX的做法，分层图，请他自己上程序，说明和注释作者: admin 时间: 2018-4-16 12:17
喻天成的做法，简单而且粗暴。注意其中不联通的在处理。