最短路径算法

转载至：http://www.cnblogs.com/myjfm/archive/2010/07/20/1781633.html

最短路径问题主要包括两大类：一是单源最短路径问题；二是每对顶点间的最短路径问题。

1、Dijkstra算法：

Dijkstra算法用于解决有向图G=(V, E)上带非负权的单源最短路径的问题：

　　设置一顶点集合S，从源点s到集合中的顶点的最终最短路径的权值均已确定。算法反复选择具有最短路径估计的不在集合S中的顶点u，并将u加入到S中，对u的所有出边进行松弛。下面算法实现中，用到了顶点的最小优先队列Q，排序关键字为顶点的d值。

1 2 3 4 5 6 7 8 9 10

Dijkstra(G, w, s) INITIALIZE-SINGLE-SOURCE(G, s) S = {}//S集合置空 Q = V[G]//Q为所有不在S中的顶点集合 P[1->n] = s;//P[i]表示最短路径中到达i节点的前任节点 whileQ != ∅ dou = EXTRACT-MIN(Q) S = S U {u} foreach vertex v which is adjacent to u doRELAX(u, v, w)

算法保持源点到每个顶点的当前已知最短路径d[];EXTRACT-MIN()就是从找出当前已知最短路径最小的顶点(这也是Dijkstra算法采用贪心思想的一个体现)。算法另一个比较重要的地方是采用了松弛技术-----RELAX(u, v, w)：

1 2 3 4

RELAX(u, v, w) ifd[u] + w(u, v) < d[v] d[v] = d[u] + w(u, v) P[v] = u

松弛技术是求最短路算法中最基本也是最核心的技术，它反复减小每个结点的实际最短路径的权的上限，直到该上限等于最短路径的权。

Dijkstra算法的时间复杂度主要取决于优先队列的实现，如果简单的用一个数组实现，则每次取最小的d[i]的操作时间是O(V)，总计运行时间为O(V*V + E) = O(V*V)。

如果用斐波那契堆来实现优先队列则可将运行时间优化到O(VlgV + E)。

2、Bellman-Ford算法：

当带权有向图中边的权值有负值的时候，Dijjstra算法失效，如图：

这时候Bellman-Ford算法派上用场了。

Bellman-Ford算法返回一个bool值，表明图中是否存在着一个从源点可达的权为负的回路。

若存在这样的回路的话，算法说明该问题无解；若不存在这样的回路，算法将产生最短路径及其权值。

此算法同样运用松弛技术，对每个顶点，逐步减小从源s到v的最短路径权的估计值d[v]直到其达到实际最短路径的权。

1 2 3 4 5 6 7 8 9 10 11 12

BLLEMAN-FORD(G, w, s) INITIALIZE-SINGLE-SOURCE(G, s) fori = 1 to |V(G)| - 1 dofor each edge(u, v) doRELAX(u, v, w) foreach edge(u, v) doif d[v] > d[u] + w(u, v) thenreturn FALSE returnTRUE

Bellman-Ford算法对图中每条边进行|V| - 1次松弛操作，在进行了|V| - 1次松弛操作之后再进行一次松弛操作，如果发现仍然有边需要松弛，则说明有负权回路，返回FALSE。

很显然Bellman-Ford算法的运行时间为O(VE)。

3、SPFA算法(Shortest Path Faster Algorithm)：

很多时候，图中存在负权边，这时候Dijkstra算法失效，而当图中边的数量庞大的时候Bellman-Ford算法复杂度又过高，这时候SPFA算法就可以派上用场了。

SPFA算法思想：

设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作。

如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

SPFA(G, w, s)‏ INITIALIZE-SINGLE-SOURCE(G, s)‏ INITIALIZE-QUEUE(Q)‏ INQUEUE(Q,s)‏ while!Q.emtpy()‏ dou = q.front()‏ Q.pop()‏ for每条从u出发的边(u, v)‏ dotmp = d[v] relax(u, v, w)‏ if(d[v] < tmp && (v不在Q中))‏ INQUEUE(Q,v)‏

由于每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。因此只要最短路径存在，上述SPFA算法必定能求出最小值。

在SPFA的过程中，记录每一个节点的前驱节点，如果一个点入队|V|次，则沿前驱节点必可以找到一个权值为负的环。

在平均情况下，SPFA算法的期望时间复杂度为O(E)，最坏情况依然是O(VE)。

算法复杂度分析：

算法每次取出队首结点u，并访问u的所有邻接点的复杂度为O(d)，其中d为点u的出度。运用均摊分析的思想，对于|V|个点|E|条边的图，点的平均出度为|E|/|V|，所以每处理一个点的复杂度为O(E/V)。假设结点入队的次数h，显然h随图的不同而不同。但它仅与边的权值分布有关。我们设h=kV，则算法SPFA的时间复杂度在平均的情况下T = O(hE/V)= O(h/V * E) = O(k*E)，可以将k看成一个比较小的常数，所以SPFA算法在一般情况下的时间复杂度为O(E)。k的期望大小为 2。

我们对比Bellman-Ford算法和SPFA算法可以看出，其实SPFA算法其实就是Bellman-Ford算法的优化，因为Bellman-Ford算法强行使得每条边都松弛了|V|次，而SPFA算法只有在一条边可能需要松弛的时候才选择松弛，所有平均情况下SPFA算法要明显快于Bellman-Ford算法，但是最坏情况下相同。

4、Floyd-Warshall算法：

Floyd-Warshall算法用于解决每对顶点间的最短路径问题。它同样采用了松弛技术，但是思想却不是像Dijkstra算法一样采用贪心策略，它采用动态规划的思想：

对于任意两点（假设为i和j）间的最短路径（假设为p），枚举除i和j外的所有顶点k，则p要么经过k，要么不经过k。所以可以得到：

初始情况下：d[i][j] = w[i][j];

d[i]j] = min{d[i][j], d[i][k] + d[k][j]} 其中k = 1...n

1 2 3 4 5 6 7 8 9 10 11 12 13 14

/*图采用邻接矩阵存储，假设矩阵为W = d[1->n][1->n] 前驱矩阵假设为P ＝ p[1->n][1->n]*/ FLOYD-WARSHALL(W) n = rows[W] fork = 1 to n dofor i = 1 to n dofor j = 1 to n dod[i][j] = min(d[i][j], d[i][k] + d[k][j]) ifd[i][j] > d[i][k] + d[k][j] then p[i][j] = p[k][j] returnW, P

显然Floyd-Warshall算法的时间复杂度为O(n ＊ n ＊ n)。