最短带权路径问题的解法::Dijkstra & Floyd
在一个网络中，如果两个结点之间有直接的因果关系，则这两个结点直接连通，在连接
两个结点的弧上标上它的代价或权，值得注意的是这样的代价不一定是对称的，即A到B
的代价不一定等于B到A的代价，实际问题中以行船为例，有顺水和逆水的区别。在图Ｇ
中，给出两个结点求这样一条最短的路径，使经过这条路径上的代价之和最小，这就是最短
路径问题。
如果所有弧上的权都相等，则问题退化为求两个结点间的一条路径使经过的中间结点最
少。比如在一个城市的交通网络中，乘客关心的可能只是旅途中中转的次数，只希望转更少
次数的车。对于这样的问题，运用ＢＦＳ对图进行层次遍历，可以在O(n)的时间复杂度上
完成搜索，考虑到ＢＦＳ的层次遍历性质，不难理解，在此不讨论。
考虑到带权的有向图（无向图可看成特殊的有向图），如何求最短路径呢？
１、 Dijkstra算法
Dijkstra是最早提出这个算法的大牛：）。这是图论中非常有名的一个算法。
图采用邻接矩阵的形式描述，M[i][j]表示结点i到结点j间的代价，如果没有直接因果
关系，则为无穷大，计算机中可以用一个很大的数据代替。后面的Floyd算法同样这样描述。
差点忘了，dijkstra算法只能求出从结点i到其它各结点的最短路径。算法引入这样两
个集合S和Ｔ，Ｓ是那些已经确定了到Ｉ结点的最短路径的结点，在计算过程中为什么可
以确定某些结点已经到达了最短的要求了呢？后面再讲。Ｔ为全集Ｕ和Ｓ的差集，即那些还
未确定最短路径的结点。而且Ｓ的初值是{i}，Ｔ的初值是Ｕ-{i}。另外再引入一个标记数组
Ｄ[N]，其中在某一步D[k]表示当前从i到k的较短路径，D[k]的初值为M[i][k]，整个算法
过程如下：
１、 在Ｔ中选择一个Ｄ[k]最小的结点k，将k并入Ｓ，并从Ｔ中去掉，如果Ｔ为｛｝则
转到３；
２、 用k结点和Ｔ中其余结点进行一遍比较，如果D[i]>D[k]+M[k][i]，则用D[k]+M[k][i]
取代原来的Ｄ[i]，重复１；
３、 算法结束，此时Ｄ[k]中保存的就是从Ｉ到k结点的最短路径。
算法就以这样非常简单的形式完成了求解，时间复杂度是O(n^2)，确定了从Ｉ到其余
各结点的最短路径，如果要求记录路径，也很容易，可以引入一个路径标记数组P[k][m]，
如果P[k][m]为０则说明从i到k的当前最短路径中不含有m结点作为中间结点，如果为１
则m成为其路径的所经结点。
就前面提出为什么可以这样一部分一部分的确定解集Ｓ，举个例子，第一遍比较，得到
了能够直接抵达的最小代价的结点s0，为什么s0不可能含有其它路径了呢？假设从i到s0
并不是最短路径，则至少含有不是s0的结点k，使i->k->…->s0比原路径更短，而此路径比
i->k大，i->k又比i->s0大，所以不可能比i->s0小，矛盾，得证。再证在算法第k+1步时，
前一次求得了由至多k步可到达的最短路径终结点sk，有i?sk最短，在与后面剩下Ｔ中结
点的比较中，如果D[k]+M[k+1][i]更短，则替换，替换的原则是在不能与某条至多m（m<k）
步可到达的最短路径替换，为什么？在前面的过程已经替代了，所以只考虑当前的D[k+1]。
这只是我的理解，如果需要更加完善的证明还需用数学语言，略之。
与Dijkstra算法平分秋色的还有Floyd算法。
２、 Floyd算法
如果要求所有两结点间的最短路径，则可以使用dijkstra算法n次完成，时间复杂度是
O(n^3)，Floyd还提出过另一个算法，同样是O(n^3)的复杂度，但形式上更简单些。
要求的解是一个矩阵Ｓ[N][N]，其中S[i][j]表示结点i到j的最短路径，算法很像动态
规划算法，甚至更简单些，不同的是这里规划的是一个矩阵，而不是简单的数组。
Floyd算法过程描述如下：
１、 首先Ｓ以边集Ｍ初始化，得到所有的直接连通代价；
２、 依次考虑第k个结点，对于Ｓ中的每一个Ｓ[i][j]，判断是否满足：
S[i][j]>S[i][k]+S[k][j]，如果满足则用S[i][k]+S[k][j]代替Ｓ[i][j]，此为第k步；
３、 k循环取遍所有结点，算法结束时，Ｓ为最终解。
这样的求法自然再简单不过了，但要证明其中的正确性，有些难度，为什么不会使结点
重复存在于同一路径？在替换的时候，S[i][k]和S[k][j]中如果同时含有m结点，则这样的替
换显然是错误的，相当于i-->m-->k-->m-->j，可以简单用这有这样连通关系的例子试一下，会
发现如果在一条路径中有结点冗余，则不可能是最短路径，显然上面这条有冗余结点的路径
肯定要比i-->m-->j要长，所以算法在要求最短的同时已经排除了这种情况，这样使得任意一
条路径都不冗余。
最后想提一下旅行商问题，旅行商问题非常类似于最短路径问题，不同的是所求的是一
个环路，且环路还是要包含图中所有结点的，同样的要求是代价和最短。但旅行商问题是一
个ＮＰ问题，用动态规划的方法只能达到Ｏ(2^n)的复杂度。
不过就实际应用来说，我觉得最短路径更实用，对于旅行商问题只需要求到某种近似程
度的近似解已经够用了，如果降低总程代价1%需要已经花费的时间的几倍，这样的努力是
多么的廉价。
ＰＳ：自己看《数据结构》，看了一晚上才把这两个算法弄懂，凭记忆写下来的，希望
没错。
评论