最短路算法图论.ppt

* * 1）负权重下，Dijkstra无法工作。 2）负权重有用么？ 通信网中一般不会出现负权重，但是很多其他实际问题建模为最短路问题时，就会出现负权重。Robert Sedgewick在《Algorithms in Java》3rd Ed中（21.7节），就给出了一个例子。他将Hamilton路径问题转化为一个最短路问题，图中出现的权重就可能为负。 3）更糟的是，如果图中存在负圈，则最短路问题无法求解。 ?如果不强制要求解为简单路径（注意，Dijkstra算法求出的必然是简单路径），则不存在最短路，因为路径权重可以为负无穷。 ?如果要求解必须是简单路径，那么不存在多项式算法。该问题跟最长路一样，是NP-C的。 4）那怎么办？ Label-Correcting算法 注意：label-correcting算法只能检测负圈。存在负圈时，该算法是算不出最短简单路径的。当然，只要没有负圈，即使存在负权重，该算法也可以算出最短路。 * 最短路的特征：距离标记满足一定的关系。 证明这个充要条件。必要性：最短路必然满足这个条件。充分性：满足这些条件，必然得到最短路。 * 根据wikipedia，Bellman-Ford算法指的是这种O(nm)复杂度的，用FIFO实现的label-correcting算法。 复杂度：O(nm)。 问题：为什么最多n次循环就够了？为什么最后一次还有更新就说明必然存在负圈？ 假定从s到v的最短路为k+1跳。并且前一跳的顶点时u。因此s?u必然是k跳的最短路； 由于k轮后所有的k跳最短路的距离标记都已被更新为最佳，故，k轮后d(u)=d*(u) 第k+1轮检查e(u,v)时，如果d(v) d*(u) + we，那么d(v)会被更新为d*(u)+we，而这就是d*(v)。这说明 如果d(v) = d*(u) + we，那么d(v) = d*(v)，已经从另一条路径（而且该路径也必然是k+1跳）达到了最佳。 如果d(v) d*(u) + we？这不可能，因为这与该路径为最短路这一假设矛盾。 * 一开始用例子来讨论Bellman-Ford算法的运行。其中每轮循环采用什么顺序进行边的检查是任意的。 第一轮用动画讲。 第二轮让学生做。提炼出第一个idea：不必检查所有的边。 第三轮也让学生做。提示：显然只需要考虑c和e的“发出”边。显然，第四、五、六轮不必做了。引出第二个idea。 讲完了2个idea之后，给出伪码并讲解。着重指出，LIST可以实现这两个idea：只检查必要的边；且可以发现是否有必要继续（LIST为空意味着不会发生更新了） * 1）label-correcting算法中，站在每个顶点i的角度看，源点到i的距离是否更新，只取决于i的反向邻接点是否更新了。 2）反过来呢？站在每个顶点i的角度看，他到某个目的点d的最小距离是否需要更新，只取决于i的正向邻接点到d的距离标记是否发生了更新。 3）因此，只要路由器i的某个邻接点j告诉i它到其他路由器的距离（一个距离矢量），i就可以判断他到其他路由器的距离是否需要更新。 * * 应对负权重有两个困难：负圈检测和负权重。调用Bellman-Ford一次，就可以解决这两个问题。 用图来说明：采用这种权重变换后，得到的必是非负值。因为：如果是负值，就说明d(b)不是最短路距离，矛盾。 * 复杂度分析：假定权重为整数；最大权重为C 1）针对每个节点对，每轮检查需要检查n次（i，j不变，k有n种可能）； 2）最多需要多少轮？最坏情况下，每轮只更新（变小）1（因为是整数）；所以最多C轮； 3）多少个节点对？n平方。 所以最坏复杂度为n立方C。 非整数权重时，证明方法不同，但结论一样。 * 用伪码讲复杂度：全是for循环，循环次数固定。 * 2009年春季 图算法及其在通信网络中的应用 * / 55 Label-Correcting算法 负权重 1 2 3 5 一般的Label-Correcting Bellman-Ford算法 应用 2009年春季 图算法及其在通信网络中的应用 * / 55 A B C D 2 1 3 7 1 应用：距离矢量路由协议 目的 距离 端口 B 2 B C 7 C D ? - 目的 距离 端口 A 2 A C 1 C D 3 D 目的 距离 端口 A 7 A B 1 B D 1 D 顶点i 的距离标记什么时候需要更新？ 当i的反向邻接点发生了更新时。 反过来，i 到某个目的点d 的距离何时更新？ 当i 的正向邻接点到d 的距离发生了更新时。 只要i 的邻接点不断地告诉i 它们到其它目的点的距离发生了怎样的变化，i