最短路径

概述

最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。 算法具体的形式包括：

1. 确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。
2. 确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
3. 确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。
4. 全局最短路径问题 - 求图中所有的最短路径。

常用算法

用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。 最常用的路径算法有：

1. Dijkstra 算法
2. A*算法
3. SPFA 算法
4. Bellman-Ford 算法
5. Floyd-Warshall 算法
6. Johnson 算法
   所谓单源最短路径问题是指：已知图 G=（V，E），我们希望找出从某给定的源结点 S∈V 到 V 中的每个结点的最短路径。

Dijkstra 算法

概述

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。注意该算法要求图中不存在负权边。

算法描述

设 G=(V,E)是一个带权有向图，把图中顶点集合 V 分成两组，第一组为已求出最短路径的顶点集合（用 S 表示，初始时 S 中只有一个源点，以后每求得一条最短路径 , 就将加入到集合 S 中，直到全部顶点都加入到 S 中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用 U 表示），按最短路径长度的递增次序依次把第二组的顶点加入 S 中。在加入的过程中，总保持从源点 v 到 S 中各顶点的最短路径长度不大于从源点 v 到 U 中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S 中的顶点的距离就是从 v 到此顶点的最短路径长度，

U 中的顶点的距离，是从 v 到此顶点只包括 S 中的顶点为中间顶点的当前最短路径长度。

算法步骤

1. 初始时，S 只包含源点，即 $S＝{v}$，v 的距离为 0。U 包含除 v 外的其他顶点，即:U={其余顶点}，若 v 与 U 中顶点 u 有边，则<u,v>正常有权值，若 u 不是 v 的出边邻接点，则$<u,v>$权值为∞。
2. 从 U 中选取一个距离 v 最小的顶点 k，把 k，加入 S 中（该选定的距离就是 v 到 k 的最短路径长度）。
3. 以 k 为新考虑的中间点，修改 U 中各顶点的距离；若从源点 v 到顶点 u 的距离（经过顶点 k）比原来距离（不经过顶点 k）短，则修改顶点 u 的距离值，修改后的距离值的顶点 k 的距离加上边上的权。
4. 重复步骤 b 和 c 直到所有顶点都包含在 S 中。

 

示例代码（邻接表+优先队列）

#include <queue> 
#include <cstdio> 
#include <iostream> 
#define N 100 
#define M (1 << 30) 
using namespace std; 

struct Edge{ 
    int v, w, n; 
}; 

Struct Node{    
    int v, w; 
    friend bool operator < (const Node &a, const Node &b){
        return a.w > b.w; 
    } 
}; 

int head[N], dis[N], n, m, e; bool vis[N];
Edge edge[N * /2]; 
priority_queue < Node > que; 

void init(){     
    e = 0;     
    while(!que.empty()) que.pop();
    fill(head, head + N, -1);
    fill(dis, dis + N, M);     
    fill(vis, vis + N, false); 
} 

void addedge(int u, int v, int w){     
    edge[e].v = v;     
    edge[e].w = w;     
    edge[e].n = head[u];
    head[u] = e++; 
} 

void Dijkstra(int s){     
    Node t;     
    t.v = s; 
    t.w = 0;     
    dis[t.v] = t.w;     
    que.push(t);     
    while(!que.empty()){         
        t = que.top();         
        que.pop();         
        if(vis[t.v]) continue;        
        vis[t.v] = true;         
        for(int i = head[t.v]; i != -1; i = edge[i].n) 
            if(!vis[edge[i].v] && dis[edge[i].v] > dis[t.v] + edge[i].w){                 
                Node tt;                 
                tt.v = edge[i].v; 
                dis[edge[i].v] = tt.w = dis[t.v] + edge[i].w;                 
                que.push(tt); 
            } 
    } 
} 
int main(){     
    while(scanf("%d%d", &n, &m) != EOF && n){         
        init();        
        int a, b, c;         
        for(int i = 0; i < m; i++){             
            scanf("%d%d%d", &a, &b, &c);             
            addedge(a, b, c);             
            addedge(b, a, c); 
        } 
        Dijkstra(1);
        printf("%d\n", dis[n]); 
    }     
    return 0; 
} 

算法复杂度

邻接矩阵 $O(n^{2})$, 邻接表+优先队列 $O(e logv)$.

Floyd-Warshall 算法

基本操作

弗洛伊德（Floyd）算法过程：

1. 用 $D[v][w]$记录每一对顶点的最短距离。
2. 依次扫描每一个点，并以其为基点再遍历所有每一对顶点 D[][]的值，看看是否可用过该基点让这对顶点间的距离更小。

算法理解

最短距离有三种情况：

• 两点的直达距离最短。（如下图<v,x>）
• 两点间只通过一个中间点而距离最短。（图<v,u>）
• 两点间用通过两各以上的顶点而距离最短。（图<v,w>）
  对于第一种情况：在初始化的时候就已经找出来了且以后也不会更改到。对于第二种情况：弗洛伊德算法的基本操作就是对于每一对顶点，遍历所有其它顶点，看看可否通过这一个顶点让这对顶点距离更短，也就是遍历了图中所有的三角形（算法中对同一个三角形扫描了九次，原则上只用扫描三次即可，但要加入判断，效率更低）。

对于第三种情况：如下图的五边形，可先找一点（比如 x，使$<v,u>=2$），就变成了四边形问题，再找一点（比如 y,使<u,w>=2），可变成三角形问题了（v,u,w），也就变成第二种情况了，由此对于 n 边形也可以一步步转化成四边形三角形问题。（这里面不用担心哪个点要先找哪个点要后找，因为找了任一个点都可以使其变成（n－1）边形的问题）。结合代码 并参照上图所示 我们来模拟执行下 这样才能加深理解：

第一关键步骤：当 k 执行到 x，i=v,j=u 时，计算出 v 到 u 的最短路径要通过 x，此时 v、u 联通了。

第二关键步骤：当 k 执行到 u，i=v，j=y，此时计算出 v 到 y 的最短路径的最短路径为 v 到 u，再到 y(此时 v 到 u 的最短路径上一步我们已经计算过来，直接利用上步结果)。

第三关键步骤：当 k 执行到 y 时，i=v，j=w，此时计算出最短路径为 v 到 y(此时 v 到 y 的最短路径长在第二步我们已经计算出来了)，再从 y 到 w。

依次扫描每一点**(k)**，并以该点作为中介点，计算出通过 **k 点的其他任意两点(i,j)**的最短距离，这就是 **floyd **算法的精髓！

同时也解释了为什么 k 点这个中介点要放在最外层循环的原因.

动态规划的解释：

在动态规划算法中，处于首要位置、且也是核心理念之一的就是状态的定义。在这里，把 d[k][i][j]定义成：

“只能使用第 1 号到第 k 号点作为中间媒介时，点 i 到点 j 之间的最短路径长度。”

图中共有 n 个点，标号从 1 开始到 n。因此，在这里，k 可以认为是动态规划算法在进行时的一种层次，或者称为“松弛操作”。d[1][i][j]表示只使用 1 号点作为中间媒介时，点 i 到点 j 之间的最短路径长度；d[2][i][j]表示使用 1 号点到 2 号点中的所有点作为中间媒介时，点 i 到点 j 之间的最短路径长度；d[n-1][i][j]表示使用 1 号点到 (n-1)号点中的所有点作为中间媒介时，点 i 到点 j 之间的最短路径长度 d[n][i][j]表示使用 1 号到 n 号点时，点 i到点 j 之间的最短路径长度。有了状态的定义之后，就可以根据动态规划思想来构建动态转移方程。

动态转移的基本思想可以认为是建立起某一状态和之前状态的一种转移表示。按照前面的定义，d[k][i][j]是一种使用 1 号到 k 号点的状态，可以想办法把这个状态通过动态转移，规约到使用 1 号到(k-1)号的状态，即 d[k1][i][j]。对于 d[k][i][j]（即使用 1 号到 k 号点中的所有点作为中间媒介时，i 和 j 之间的最短路径），可以分为两种情况：（1）i 到 j 的最短路不经过 k；（2）i 到 j 的最短路经过了 k。不经过点 k 的最短路情况下，$d[k][i][j]=d[k1][i][j]$。经过点 k 的最短路情况下，$d[k][i][j]=d[k-1][i][k]+d[k-1][k][j]$。因此，综合上述两种情况，便可以得到 Floyd 算法的动态转移方程：$$d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j]) (k,i,j \epsilon [1,n])$$

最后，d[n][i][j]就是所要求的图中所有的两点之间的最短路径的长度。在这里，需要注意上述动态转移方程的初始（边界）条件，即 d[0][i][j]=w(i, j)，也就是说在不使用任何点的情况下（“松弛操作”的最初），两点之间最短路径的长度就是两点之间边的权值（若两点之间没有边，则权值为 INF，且我比较偏向在 Floyd 算法中把图用邻接矩阵的数据结构来表示，因为便于操作）。当然，还有 $d[i][i]=0(i\epsilon [1,n])$。

这样我们就可以编写出最为初步的 Floyd 算法代码：

void floyd_original() {     
    for(int i = 1; i <= n; i++)         
        for(int j = 1; j <= n; j++)             
            d[0][i][j] = graph[i][j];     
    for(int k = 1; k <= n; k++) {         
        for(int i = 1; i <= n; i++) {             
            for(int j = 1; j <= n; j++) { 
                d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]); 
            } 
        }     
    } 
}

几乎所有介绍动态规划中最为著名的“0/1 背包”问题的算法书籍中，都会进一步介绍利用滚动数组的技巧来进一步减少算
的空
间复杂度，使得 0/1 背包只需要使用一维数组就可以求得最优解。而在各种资料中，最为常见的 Floyd 算法也都是用了二维数组来表示状态。那么，在 Floyd 算法中，是如何运用滚动数组的呢？

再次观察动态转移方程 $$d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j])$$ 可以发现每一个第 k 阶段的状态（d[k][i][j]），所依赖的都是前一阶段（即第 k-1 阶段）的状态（如 d[k-1][i][j]，d[k-1][i][k]和 d[k-1][k][j]）。

右图描述了在前面最初试的 Floyd 算法中，计算状态 d[k][i][j]时，d[k-1][][]和 d[k][][]这两个二维数组的情况（d[k-1][][]表示第 k-1 阶段时，图中两点之间最短路径长度的二维矩阵；d[k][][]表示第 k 阶段时，图中两点之间最短路径长度的二维矩阵）。红色带有箭头的有向线段指示了规划方向。灰色表示已经算过的数组元素，白色代表还未算过的元素。由于 d[k-1][][]和 d[k][][]是两个相互独立的二维数组，因此利用 d[k-1][i][j]，d[k-1][i][k] 和 d[k-1][k][j]（皆处于上方的二维数组中）来计算 d[k][i][j]时没有任何问题。

那如何利用一个二维数组来实现滚动数组，以减小空间复杂度呢？

右图是使用滚动数组，在第 k 阶段，计算 d[i][j]时的情况。此时，由于使用 d[][]这个二维数组作为滚动数组，在各个阶段的计算中被重复使用，因此数组中表示阶段的那一维也被取消了。在这图中，白色的格子，代表最新被计算过的元素（即第 k 阶段的新值），而灰色的格子中的元素值，其实保存的还是上一阶段（即第 k-1 阶段）的旧值。因此，在新的 d[i][j]还未被计算出来时，d[i][j]中保存的值其实就对应之前没有用滚动数组时 d[k-1][i][j] 的值。此时，动态转移方程在隐藏掉阶段索
引后就变为：$$d[i][j] = min(d[i][j], d[i][k]+d[k][j]) (k,i,j\epsilon [1,n])$$ 赋值号左侧 d[i][j]就是我们要计算的第 k 阶段是 i 和 j 之间的最短路径长度。在这里，需要确保赋值号右侧的d[i][j], d[i][k]和 d[k][j]的值是上一阶段（k-1 阶段）的值。前面已经分析过了，在新的 d[i][j]算出之前，d[i][j]元素保留的值的确就是上一阶段的旧值。但至于 d[i][k]和 d[k][j]呢？我们无法确定这两个元素是落在白色区域（新值）还是灰色区域（旧值）。好在有这样一条重要的性质，dp[k-1][i][k]和 dp[k-1][k][j]是不会在第 k 阶段改变大小的。也就是说，凡是和 k 节点相连的边，在第 k 阶段的值都不会变。如何简单证明呢？我们可以把 j=k 代入之前的$$ d[k][i][j]=min(d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j]) $$方程中，即：

$$d[k][i][k]

= min(d[k-1][i][k], d[k-1][i][k]+d[k-1][k][k])

= min(d[k-1][i][k], d[k-1][i][k]+0)

= d[k-1][i][k]$$

也就是说在第 k-1 阶段和第 k 阶段，点 i 和点 k 之间的最短路径长度是不变的。相同可以证明，在这两个阶段中，点 k 和点 j 之间的的最短路径长度也是不变的。因此，对于使用滚动数组的转移方程$$ d[i][j] = min(d[i][j], d[i][k]+d[k][j]) $$来说，赋值号右侧的 d[i][j], d[i][k]和 d[k][j]的值都是上一阶段（k-1 阶段）的值，可以放心地被用来计算第 k 阶段时 d[i][j]的值。

利用滚动数组改写后的 Floyd 算法代码如下：

void floyd() {     
    for(int k = 1; k <= n; k++)         
        for(int i = 1; i <= n; i++)            
            for(int j = 1; j <= n; j++)  
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
} 

因此，通过这篇文章的分析，我们可以发现，Floyd 算法的的确确是一种典型的动态规划算法；理解 Floyd 算法，也可以帮助我们进一步理解动态规划思想。

示例代码（含记录路径）

#include <stack> 
#include <cstdio> 
#include <iostream> 
#define M (1 << 20) 
#define N 1000 
using namespace std; 

int mp[N][N], path[N][N]; 
int n, m; 

void floyd(){    
    for(int i = 0; i < n; i++)              // 初始化 path 数组         
        for(int j = 0; j < n; j++)             
            path[i][j] = i;     
    for(int k = 0; k < n; k++){ 
        for(int i = 0; i < n; i++)             
            for(int j = 0; j < n; j++)                 
                if(mp[i][k] + mp[k][j] < mp[i][j]){                     
                    mp[i][j] = mp[i][k] + mp[k][j];                     
                    path[i][j] = path[k][j]; 
                } 
    } 
} 

int main(){     
    while(scanf("%d%d", &n, &m) != EOF){ 

        /* 输入图 */ 
        for(int i = 0; i < n; i++)             
            for(int j = 0; j < n; j++){                 
                scanf("%d", &mp[i][j]);                 
                mp[i][j] = mp[i][j]; 
            } 

        /* 求解 */         
        floyd(); 

        /* 输出 */ 
        printf("Origin -> Dest      Distance        Path\n");        
        for(int i = 0; i < n; i++){             
            for(int j = 0; j < n; j++){                 
                if(i == j) continue;                 
                printf("     %d -> %d          ", i + 1, j + 1);                 
                if(mp[i][j] == M) printf("No answer\n");                 
                else printf("%2d             ", mp[i][j]);                 
                stack <int> sta;                 
                int k = j;                 
                do{                     
                    k = path[i][k];                     
                    sta.push(k);                 
                }while(k != i); 
                while(!sta.empty()) printf("%d -> ", sta.top() + 1), sta.pop();                 
                printf("%d\n", j + 1); 
            }        					
        }     
    }
    return 0; 
} 

用 **Floyd **算法思想求最小环

Floyd 算法在进行时会不断更新矩阵 dist(k)。设 dist[k，i，j]表示从结点 i 到结点 j 且满足所有中间结点，它们均属于集合{1，2，⋯ ，k}的一条最短路径的权。其中 dist[0，i,j ]即为初始状态 i 到 j 的直接距离。对于一个给定的赋权有向图， 求出其中权值和最小的一个环。我们可以将任意一个环化成如下形式：u->k->v ->(x1-> x2-> ⋯ xm1)-> u(u 与 k、k 与 v 都是直接相连的)，其中 v ->(x1-> 2-> ⋯ m)-> u 是指 v 到 u 不经过 k 的一种路径。

在 u，k，v 确定的情况下，要使环权值最小， 则要求 (x1 一>x2->⋯一>xm)->u 路径权值最小．即要求其为 v 到 u 不经过 k 的最短路径，则这个经过 u，k，v 的环的最短路径就是：[v 到 u 不包含 k 的最短距离]+dist[O， u，k]+dist[O，k，v]。我们用 Floyd 只能求出任意 2 点间满足中间结点均属于集合{1，2，⋯ ，k}的最短路径，可是我们如何求出 v 到 u 不包含 k 的最短距离呢?

现在我们给 k 加一个限制条件：k 为当前环中的序号最大的节点(简称最大点)。因为 k 是最大点，所以当前环中没有任何一个点≥k，即所有点都 < k。因为 v->(x1->x2->……xm)->u 属于当前环，所以 x1，x2，⋯ ， xm < k，即 x1，x2．⋯。xm≤k-1。这样，v 到 u 的最短距离就可以表示成 dist[k - 1 ,u,v]。dist[k - 1,v,u]表示的是从 v 到 u 且满足所有中间结点均属于集合{1，2，⋯ ，k - 1}的一条最短路径的权。接下来，我们就可以求出 v 到 u 不包含 k 的最短距离了。这里只是要求不包含 k，而上述方法用的是 dist[k - 1，v，u]，求出的路径永远不会包含 k+l，k+2，⋯ 。万一所求的最小环中包含 k+1，k+2，⋯ 怎么办呢?的确，如果最小环中包含比 k 大的节点，在当前 u,k,v 所求出的环显然不是那个最小环。然而我们知道，这个最小环中必定有一个最大点 kO，也就是说，虽然当前 k 没有求出我们所需要的最小环，但是当我们从 k 做到 kO 的时候，这个环上的所有点都小于 kO 了．也就是说在 k=kO 时一定能求出这个最小环。我们用一个实例来说明：假设最小环为 1—3—4—5—6—2—1。的确，在 u=l，v=4，k=3 时，k<6，dist[3，4，1]的确求出的不是 4—5—6—2—1 这个环，但是，当 u=4，v=6，k=5 或 u=5，v=2，k=6 时，dist[k，v，u]表示的都是这条最短路径.所以我们在 Floyd 以后，只要枚举 u, v, k 三个变量即可求出最小环。时间复杂度为 O(n3)。我们可以发现，Floyd 和最后枚举 u, v, k 三个变量求最小环的过程都是 u,v,k 三个变量，所以我们可以将其合并。这样，我们在 k 变量变化的同时，也就是进行 Floyd 算法的同时，寻找最大点为 k 的最小环。

示例代码

#include <cstdio> 
#include <iostream> 
#include <algorithm> 
#define N 1100 
#define M (1 << 29) 
using namespace std; 

int mp[N][N], dis[N][N]; 
int path[N], pre[N][N]; 
int n, m, minc, num; 

void init(){ 
    for(int i = 0; i <= n; i++)         
        for(int j = 0; j <= n; j++){             
            mp[i][j] = M;             
            dis[i][j] = M;             
            pre[i][j] = i; 
        }
    int a, b, w;
    for(int i = 0; i < m; i++){ 
        scanf("%d%d%d", &a, &b, &w);
        if(w < mp[a][b])
            dis[a][b] = dis[b][a] = mp[a][b] = mp[b][a] = w; 
    } 
} 

void Floyd(){
    minc = M;
    for(int k = 1; k <= n; k++){
        for(int i = 1; i < k; i++)
            for(int j = i + 1; j < k; j++)
                if(minc > dis[i][j] + mp[j][k] + mp[k][i]){
                    minc = dis[i][j] + mp[j][k] + mp[k][i];
                    num = 0;
                    int t = j;
                    while(t != i){
                        path[num++] = t;
                        t = pre[i][t];
                    }
                    path[num++] = i;
                    path[num++] = k;
                } 
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(dis[i][j] > dis[i][k] + dis[k][j]){
                    dis[i][j] = dis[i][k] + dis[k][j];
                    pre[i][j] = pre[k][j]; 
                } 
    } 
} 

int main(){
    while(scanf("%d%d", &n, &m) !=EOF){
        init();
        Floyd();
        if(minc == M) printf("No solution.\n");
        else{
            printf("%d", path[0]);
            for(int i = 1; i < num; i++)
                printf(" %d", path[i]);
            printf("\n"); 
        } 
    } 
    return 0; 
} 

复杂度分析

$O(n ^{3})$

Bellman-Ford 算法

简述

Bellman-ford 算法是求含负权图的单源最短路径算法，效率很低，但代码很容易写。即进行不停地松弛每次松弛把每条边都更新一下，若 n-1 次松弛后还能更新，则说明图中有负环，无法得出结果，否则就成功完成。Bellmanford 算法有一个小优化：每次松弛先设一个旗帜 flag，初值为 FALSE，若有边更新则赋值为 TRUE，最终如果还是 FALSE 则直接成功退出。Bellman-ford 算法浪费了许多时间做无必要的松弛。Dijkstra 算法中不允许边的权是负权，如果遇到负权，则可以采用 Bellman-Ford 算法。

Bellman-Ford 算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 G=（V,E），其源点为 s，加权函数 w 是 边集 E 的映射。对图 G 运行 Bellman-Ford 算法的结果是一个布尔值，表明图中是否存在着一个从源点 s 可达的负权回路。若不存在这样的回路，算法将给出从源点 s 到 图

G 的任意顶点 v 的最短路径 d[v]。

适用条件**&**范围

1.单源最短路径(从源点 s 到其它所有顶点 v);

2.有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集 E 的有向图);

3.边权可正可负(如有负权回路输出错误提示);

4.差分约束系统;

**Bellman-Ford **算法描述

1,.初始化：将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0;

2.迭代求解：反复对边集 E 中的每条边进行松弛操作，使得顶点集 V 中的每个顶点 v 的最短距离估计值逐步逼近其最短距离；（运行|v|-1 次）

3.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回 true，并且从源点可达的顶点 v 的最短距离保存在 d[v]中。

算法证明

首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1 条边。   其次，从源点 s 可达的所有顶点如果 存在最短路径，则这些最短路径构成一个以 s 为根的最短路径树。

Bellman-Ford 算法的迭代松弛操作，实际上就是按顶点距离 s 的层次，逐层生成这棵最短路径树的过程。

在对每条边进行 1 遍松弛的时候，生成了从 s 出发，层次至多为 1 的那些树枝。也就是说，找到了与 s 至多有 1 条边相联的那些顶点的最短路径；对每条边进行第 2 遍松弛的时候，生成了第 2 层次的树枝，就是说找到了经过 2 条边相连的那些顶点的最短路径……。因为最短路径最多只包含|v|-1 条边，所以，只需要循环|v|-

1 次。

每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后这层顶点的最短距离值就会一直保持不变，不再受后续松弛操作的影响。（但是，每次还要判断松弛，这里浪费了大量的时间，怎么优化？单纯的优化是否可行？）   如果没有负权回路，由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1 遍松弛操作后，所有从 s 可达的顶点必将求出最短距离。如果 d[v]仍保持 +∞，则表明从 s 到 v 不可达。

如果有负权回路，那么第 |v|-1 遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。

图解算法

首先介绍一下松弛计算。如图：松弛计算之前，点 B 的值是 8，但是点 A 的值加上边上的权重 2，得到 5，比点 B 的值（8）小，所以，点 B 的值减小为 5。这个过程的意义是，找到了一条通向 B 点更短的路线，且该路线是先经过点 A，然后通过权重为 2 的边，到达点B。

Bellman－Ford 算法可以大致分为三个部分

第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为 0，其它的点的值设为无穷大（表示不可达）。

第二，进行循环，循环下标为从 1 到 n－1（n 等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。

第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况：

d（v） > d (u) + w(u,v)

则返回 false，表示途中存在从源点可达的权为负的回路。

之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。

考虑右图：

经过第一次遍历后，点 B 的值变为 5，点 C 的值变为 8，这时，注意权重为－10 的边，这条边的存在，导致点 A 的值变为－2。（8＋ －10＝－2）第二次遍历后，点 B 的值变为 3，点 C 变为 6，点 A 变为－4。正是因为有一条负边在回路中，导致每次遍历后，各个点的值不断变小。

在回过来看一下 bellman－ford 算法的第三部分，遍历所有边，检查是否存在 d（v） > d (u) + w(u,v)。因为第二部分循环的次数是定长的，所以如果存在无法收敛的情况，则肯定能够在第三部分中检查出来。比如此时，点 A 的值为－2，点 B 的值为 5，边 AB 的权重为 5，5 > -2 + 5. 检查出来这条边没有收敛。

所以，Bellman－Ford 算法可以解决图中有权为负数的边的单源最短路径问。

示例代码

#include <stack> 
#include <cstdio>   
#include <iostream>   
#include <algorithm> 
#define N 1010   
#define MAX 0x3f3f3f3f
using namespace std;   

int n, m, s; //点，边，起点   

struct Edge{ //边       
    int u, v;
    int cost;   
};   

Edge edge[N];
int dis[N], pre[N];   

bool Bellman_Ford(){
    for(int i = 1; i <= n; ++i) //初始化
        dis[i] = (i == s ? 0 : MAX);
    for(int i = 1; i <= n - 1; ++i)
        for(int j = 1; j <= m; ++j)
            if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost){ //松弛（顺序一定不能反~）
                dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
                pre[edge[j].v] = edge[j].u; 
            }
    bool flag = 1; //判断是否含有负权回路   
    for(int i = 1; i <= m; ++i)
        if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost){
            flag = 0;
            break;
        }
    return flag;   
}   

void print_path(int root){ //打印最短路的路径
    stack <int> sta;
    while(root != pre[root]){ //前驱
        sta.push(root);
        root = pre[root];
    }
    printf("%d", root);
    while(!sta.empty()){
        printf(" -> %d", sta.top());
        sta.pop(); 
    }
    printf("\n"); 
}   

int main(){   
    while(~scanf("%d%d%d", &n, &m, &s)){
        fill(pre, pre + N, 0);
        pre[s] = s;
        for(int i = 1; i <= m; ++i){
            scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);   
        }
        if(Bellman_Ford())
            for(int i = 1; i <= n; ++i){ //每个点最短路
                if(dis[i] == MAX){
                    printf("From %d to %d no way!\n", s, i);
                    continue; 
                }
                printf("From %d to %d : %d\n", s, i, dis[i]);
                printf("Path: ");
                print_path(i);   
            }
        else  printf("have negative circle\n");
        printf("\n\n"); 
    } 
    return 0;   
}   

复杂度分析

O(VE)

SPFA 算法

简述

SPFA(Shortest Path Faster Algorithm)是 Bellman-Ford 算法的一种队列实现，减少了不必要的冗余计算。 SPFA——Shortest Path Faster Algorithm，它可以在 O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。SPFA 的实现甚至比 Dijkstra 或者 Bellman_Ford 还要简单。

算法描述

设 Dist 代表 S 到 I 点的当前最短距离，Fa 代表 S 到 I 的当前最短路径中 I 点之前的一个点的编号。开始时 Dist 全部为+∞，只有 Dist[S]=0，Fa 全部为 0。

维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点 S。用一个布尔数组记录每个点是否处在队列中。

每次迭代，取出队头的点 v，依次枚举从 v 出发的边 v->u，设边的长度为 len，判断 Dist[v]+len 是否小于 Dist[u]，若小于则改进 Dist[u]，将 Fa[u]记为 v，并且由于 S 到 u 的最短距离变小了，有可能 u 可以改进其它的点，所以若 u 不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是 S 到所有的最短距离都确定下来，结束算法。若一个点入队次数超过 n，则有负权环。

SPFA 在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是 SPFA 中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为 k，有办法证明对于通常的情况，k 在 2 左右。

SPFA 算法（Shortest Path Faster Algorithm），也是求解单源最短路径问题的一种算法，用来解决：给定一个加权有向图 G 和源点 s，对于图 G 中的任意一点 v，求从 s 到 v 的最短路径。 SPFA 算法是 Bellman-Ford 算法的一种队列实现，减少了不必要的冗余计算，他的基本算法和 Bellman-Ford 一样，并且用如下的方法改进： 1、第二步，不是枚举所有节点，而是通过队列来进行优化 设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点 u，并且用 u 点当前的最短路径估计值对离开 u 点所指向的结点 v 进行松弛操作，如果 v 点的最短路径估计值有所调整，且 v 点不在当前的队列中，就将 v 点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。 2、同时除了通过判断队列是否为空来结束循环，还可以通过下面的方法： 判断有无负环：如果某个点进入队列的次数超过 V 次则存在负环（SPFA 无法处理带负环的图）。

示例代码

#include <queue>
#include <stack>
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 3010;
const int MAX_INT = (1 << 29);

struct Edge{
    int v, w, nxt;
};
int n, m, ecnt;
bool vis[MAXN];
Edge edge[MAXN * MAXN];
int head[MAXN], cnt[MAXN], dis[MAXN], path[MAXN];
void init(){
    ecnt = 0;
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));
    memset(edge, 0, sizeof(edge));
    memset(head, -1, sizeof(head));
    fill(cnt, cnt + MAXN, MAX_INT);
    for(int i = 0; i < MAXN; i++)
        path[i] = i;
}
void addEdge(int u, int v, int w){
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].nxt = head[u];
    head[u] = ecnt++;
}
bool SPFA(int s){
    queue <int> que;
    vis[s] = true;
    que.push(s);
    dis[s] = 0;
    while(!que.empty()){
        int u = que.front();
        que.pop();
        vis[u] = false;
        cnt[u]++;
        if(cnt[u] > n) return false;
        for(int i = head[u]; i + 1; edge[i].nxt){
            int v = edge[i].v;
            if(dis[v] > dis[u] + edge[i].w){
                dis[v] = dis[u] + edge[i].w;
                path[v] = u;
                if(!vis[v]){
                    vis[v] = true;
                    que.push(v);
                }
            }
        }
    }
}
void PrintPath(int t){
    stack <int> sta;
    while(t != path[t]){
        sta.push(t);
        t = path[t];
    }
    printf("%d ", t);
    while(!sta.empty()){
        printf("%d ", sta.top());
        sta.pop();
    }
    printf("\n");
}

复杂度分析

O(E)