四种常用最短路径算法模板

转自：http://www.cnblogs.com/genyuan/archive/2013/05/01/3053904.html

最短路径算法中，有四种算法是最常见的，分别是Dijkstra算法，Floyd算法，Bellman-Ford算法和SPFA算法。

Dijkstra算法，求单源最短路径最稳定的一个算法，算法复杂度为O（n2），但可以通过队列优化。下面列出的模板是最原始的Dijkstra算法。以需要求的源为中心，向四周扩散，第一次求出的是与源直接相连接的点的距离。求出这些距离中的最短距离，然后通过这个点将与它相连接的点的最短距离更新，然后再求出现在的最短距离，如此这样下去，直到所有的点都已经被遍历过为止。已经求出最短距离的点不在参与更新。具体模板如下(以POJ3268为例）:

Floyd算法其实是Floyd-Warshall算法的简称。分以下两步进行。

1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。

Floyd算法是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。

具体模板如下所示（以POJ2240为例）:

Bellman-Ford算法

1、以下操作循环执行至多n-1次，n为顶点数： 2、对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值；     若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；

3、为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。

具体模板如下所示：

SPFA算法其实就是Bellman-Ford算法，只是它用队列进行了优化。用队列进行优化有三种形式：

1、简单地用队列进行存储。

2、SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾。

3、LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i    

    出对进行松弛操作。

以下模板是针对第一种情况（POJ3268为例）：