算法合集之《最短路算法其应用》.ppt

最短路算法及其应用 广东北江中学 余远铭 yyming@ 定义 重要性质 推论 松弛技术 常用算法 Dijkstra算法 Dijkstra算法 Bellman-Ford算法 Bellman-Ford算法 SPFA算法 SPFA算法 小结 例一 双调路径 (BOI2002) 如今的道路密度越来越大，收费也越来越多，因此选择最佳路径是很现实的问题。城市的道路是双向的，每条道路有固定的旅行时间以及需要支付的费用。路径由连续的道路组成。总时间是各条道路旅行时间的和，总费用是各条道路所支付费用的总和。同样的出发地和目的地，如果路径A比路径B所需时间少且费用低，那么我们说路径A比路径B好。对于某条路径，如果没有其他路径比它好，那么该路径被称为最优双调路径。这样的路径可能不止一条，或者说根本不存在。 给出城市交通网的描述信息，起始点和终点城市，求最优双条路径的条数。城市不超过100个，边数不超过300，每条边上的费用和时间都不超过100。 例一 双调路径 (BOI2002) 这道题棘手的地方在于标号已经不是一维，而是二维，因此不再有全序关系。我们可以采用拆点法，让d[i,c]表示从s到i费用为c时的最短时间。 例一 双调路径 (BOI2002) 例一 双调路径 (BOI2002) 两个算法在空间上是同阶的，一样是O(E)。虽然算法一仅用到二叉堆，并不是特别复杂，但是因为要用两个堆，建立更新删除写起来还是有一定的工作量的。SPFA算法写起来极其简单，效率又高，而且适用范围广（可以处理含有负权的图），在很多情况下，是最短路问题上好的选择。 例二 网络提速 (经典问题) 某学校的校园网由n(1=n=50)台计算机组成，计算机之间由网线相连，其中顶点代表计算机，边代表网线。不同网线的传输能力不尽相同。 现学校购买了m(1=m=10)台加速设备，每台设备可作用于一条网线，使网线上传输信息用时减半。多台设备可用于同一条网线，其效果叠加。 如何合理使用这些设备，使计算机1到计算机n传输用时最少，这个问题急需解决。校方请你编程解决这个问题。 例二 网络提速 (经典问题) 如图，若n=5，m=2，则将两台设备分别用于1-3，3-5的线路，传输用时可减少为22秒，这是最佳解。 例二 网络提速 (经典问题) 让我们重新描述一下问题： 给定含有n个顶点的带权无向图，一共可以进行m次操作，每次操作将一条边的权值除以2。问每次应该对哪条边进行操作，使得1到n的最短路径权和最小。 例二 网络提速 (经典问题) 例二 网络提速 (经典问题) 例二 网络提速 (经典问题) 例二 网络提速 (经典问题) 例二 网络提速 (经典问题) 结语 我们从理论上研究问题的最终目的是更好地指导实践。 在题目中，往往不会直接告诉你，什么元素应该作为结点，什么元素应该作为边，应该如何构图。这就需要你根据题目的自身的特点，借鉴以往的解题经验，运用所学的相关知识，抽象出合适的模型，利用效率已有公论的算法高效求解。 实际中遇到的题目可能千奇百怪，模型的转化千变万化，从而导致解法也多种多样，不拘一格，本文实在难以涵盖万一，只要能对读者有所启发，那么我的目的也就达到了。 * * 最短路问题是图论中的核心问题之一，它是许多更深层算法的基础。同时，该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题。 乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并在地图上标出了每对十字路口之间的距离，如何找出这一最短行程？ 一个在生活中常见的例子是: 一种可能的方法是枚举出所有路径，并计算出每条路径的长度，然后选择最短的一条。 然而我们很容易看到，即使不考虑含回路的路径，依然存在数以百万计的行车路线! 实际上，其中绝大多数路线我们是没必要考虑的。 这时候，我们应该用一种系统的方法来解决问题，而不是通常人们所用的凑的方法和凭经验的方法。 在最短路问题中，给出的是一有向加权图G=(V,E)，在其上定义的加权函数W:E→R为从边到实型权值的映射。路径P=(v0, v1,……, vk)的权是指其组成边的所有权值之和： 定义u到v间最短路径的权为： 从结点u到结点v的最短路径定义为权 的任何路径。 在乘车旅行的例子中，我们可以把公路地图模型化为一个图：结点表示路口，边表示连接两个路口的公路，边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。 边的权常被解释为一种度量方法，而不仅仅是距离。它们常常被