(最短路径算法.docVIP

6.3.3 最短路径算法--Dijkstra算法，Bellmanford算法，Floyd算法，Johnson算法 最短路径算法 在交通地图上，两地点之间的路径通常标有长度，我们可以用加权有向来描述地图上的交通网。加权有向图中每条路径都有一个路径权值，大小为该路径上所有边的权值之和。本节将重点讨论顶点之间最短路径问题。在实际问题中，路径权值还可以表示其它类型的开销，例如两地之间行程所需要的时间；两任务切换所需代价等。 本节讨论的最短路径具有方向性，问题用图的术语描述为：给定一个起始顶点s和一个结束顶点t，在图中找出从s到t的一条最短路径。称s为路径源点，t为路径汇点。 最短路径问题可以进一步分为单源最短路径和全源最短路径。 ??单源最短路径定义为，给定起始顶点s，找出从s到图中其它各顶点的最短路径。求解单源最短路径的算法主要是Dijkstra算法和Bellman-Ford算法，其中Dijkstra算法主要解决所有边的权为非负的单源最短路径问题，而Bellman-Ford算法可以适用于更一般的问题，图中边的权值可以为负。 ??全源最短路径定义为，找出连接图中各对顶点的最短路径。求解全源最短路径的算法主要有Floyd算法和Johonson算法，其中Floyd算法可以检测图中的负环并可以解决不包括负环的图中的全源最短路径问题；Johonson算法同样也是解决不包含负环的图的全源最短路径问题，但是其算法效率更高。 1 基本原则 最短路径算法具有最短路径的最优子结构性质，也就是两顶点之间的最短路径包括路径上其它顶点的最短路径。具体描述为：对于给定的带权图G=(V, E)，设p=v1, v2, …,vk是从v1到vk的最短路径，那么对于任意i和j，1≤i≤j≤k，pij=vi, vi+1, …, vj为p中顶点vi到vj的子路径，那么pij是顶点vi到vj的最短路径。 最短路径算法都使用了松弛(relaxation)技术。开始进行一个最短路径算法时，只知道图中边和权值。随着处理逐渐得到各对顶点的最短路径的信息。算法会逐渐更新这些信息，每步都会检查是否可以找到一条路径比当前给定路径更短。这一过程通常称为“松弛”。 如图为单元最短路径算法的松弛操作。问题为求求解顶点s到图中各顶点之间的最短路径，用d[i]表示顶点s到顶点i的最短路径的长度。对权值为1的边(v, w)进行松弛，若当前到顶点v和w的最短路径的长度分别6和8，如图(a)，则此时d[w]d[v]+ ω(v, w)，所以对d[w]的值需要减小，并且s到顶点w的最短路径为顶点s到v的最短路径，再经过边(v, w)，如图(b)。 我们用d[i]数组表示顶点s到顶点i的最短路径的长度，用p[i]表示顶点i在最短路径中的父顶点。可以将边松弛过程用一下代码来描述： Relax(v, w, ω(v, w))if d[w]d[v] + ω(v, w) {d[w]=d[v] + ω(v, w); p[w] = v;} 2 单源最短路径 单源最短路径定义为，给定起始顶点s，找出从s到图中其它各顶点的最短路径。这里我们将得到的结果称为最短路径树(shortest path tree)，其中树根为起始顶点s。 2.1 Dijkstra算法 在前面章节中讨论最小支撑树时，我们讨论了Prim算法：每次选择一条边添加到最小支撑树MST中，这条边连接当前MST中某个顶点和尚未在MST中的某个顶点，其权值最小。采用类似的方案可以计算最短路径树SPT。开始时将源点添加到SPT中，然后，每次增加一条边来构建SPT，所取的边总是可以给出从源点到尚未在SPT中某个定点的最短路径。这样，顶点按照到源点的距离由小到大逐个添加到SPT中。这种算法称为Dijkstra算法，具体的实现跟Prim类型，分为普通实现和基于最小堆的实现。 首先，我们需要明确Dijkstra算法的适用范围是权值非负的图，即解决带有非负权值的图中的单源最短路径问题。下面对这一属性做简单分析。 给定顶点s，通过Dijkstra算法得到的最短路径树中，从根s到树中各顶点u的树路径对应着图中从顶点s到顶点u的最短路径。归纳证明如下： 假设当前所得到的子树具有这一属性，向当前子树中添加新的顶点u，满足：从顶点s出发，经过当前SPT中的树路径，并最终到达u。可以通过选择，使得所选择的s到u的路径比所有满足条件的路径都更短。所以增加一个新的顶点将增加到达该顶点的一条最短路径。 如果边的权值可以为负数，那么上述证明过程将不成立，上述证明中已经假设了向当前子树中添加新的边时，路径的长度不会递减。然而在具有负权值的边的图中，这个假设不能满足，因为所遇到的任何边都可能指向子树中的某个顶点，而且这条边可能有一个负权值，从而会使得到达该顶点的路