上次讲到，没有负权边的有向图或无向图，可以使用迪杰斯特拉算法求出单源最短路径。如果没吃透迪杰斯特拉算法，请移步迪杰斯特拉算法
然而，有负权边时，则有可能正确，也有可能不正确。我们可以用下图来解释：
比如我们从A出发，按迪杰斯特拉算法，找到最短的是C，路径长度为1。注意，此时C点的路径长度是不能再更改的。从C出发松弛B。则得到A到B C的最短路径长度分别为1 1。但显然，A到C的最短路径A-B-C长度为2+(-2)=0。
问题就出在，迪杰斯特拉算法中，当一个顶点被认为已计算出最短路径之后，则不能再更改。所以，刚才的图中，无法通过B来松弛C。
于是在这种有负权边的图中，迪杰斯特拉算法是失效的，除非这个图是一个有向无环图。当然，有向无环图是犯不着迪杰斯特拉算法的，直接用拓扑排序或记忆化搜索即可。
今天就来解决这个问题，图中有负权边时，有两种可行的算法，分别是bellman-ford和SPFA。
文章目录
-
-
- 特别注意！！！
- 一、有向图存在最短路径的条件
- 二、贝尔曼-福特算法简介
- 三、算法详解
- 四、算法效率分析
-
特别注意！！！
bellman-ford算法和spfa算法主要适用于有向图。如果是无向图，有负权边就意味着最短路不存在，因为可以沿着这条负权边不断往返，使得路径长度不断减小。或者，可以这样思考：无向图，可以把每一边拆成方向相反的两条有向边，如果某一条无向边是负权边，则拆成两条方向相反的有向负权边，这两条边就构成一个负权环，所以最短路径不存在。
无向图不允许存在负权边，bellman-ford和spfa的时间复杂度又过高，所以对于无向图和非负权有向图，应该避免使用SPFA和bellman-ford，而应该使用迪杰斯特拉。如果是有向无环图，则应该使用拓扑排序。
关于最短路径的进一步思考，请参考最短路径，这里深入探讨了关于无向图存在负权边的情况。
一、有向图存在最短路径的条件
首先来看一下，有向图什么时候不存在最短路径。比如下图：
我们看，从C到A的最短路径。是1吗？大错特错。如果你说是1，那你没考虑这个三角形的特殊性。如果我沿着C-A-B-C-A，这条路径，长度是多少呢？立刻变成了0！那是不是0呢？还是不对。如果是C-A-B-C-A-B-C-A，又变成-1了！也就是说，这个三角形可以无穷多次环绕，使得最短路径长度为负无穷！
关键就在于，整个这个三角形三条有向边之和是个负数（所谓的负权环），也就是说，每沿着三角形绕一圈，路径长度都会减小！所以，这个最短路径长度就是负无穷大，也就是说不存在最短路径。
综上，我们可知，一个有向图中，任意两点间（如果可达的话）有最短路径的条件，就是图中没有负权环。所以我们说有向无环图必存在最短路径（不仅存在最短路径，还存在最长路径），因为它连环都没有，更不要说负权环了。
二、贝尔曼-福特算法简介
bellman-ford算法是一个求任意情况下有向图中最短路径的算法，能解决负权边问题，并且能判断是否有负权环。它的优点是思路简单，编码量小，缺点是时间复杂度高。
和迪杰斯特拉算法不同。迪杰斯特拉算法是贪心思想，每次利用当前最短路径长度对应的顶点，来更新和它相邻的结点。贝尔曼-福特算法则是搜索思想，每次利用所有的边，更新所有的结点；重复这种操作V-1次（V为顶点个数）。如果更新了V-1次，仍然有顶点可被更新，则表明存在负权环，最短路径不存在。显然，贝尔曼-福特算法的时间复杂度是 O ( V E ) O(VE) O(VE)，比迪杰斯特拉算法高得多。
三、算法详解
算法的关键步骤：
第一步，设置一个数组len，存储源点S到其它所有点的最短距离。把它所有元素都初始化为一个很大的数（比如
INT_MAX
）。并让
len[s]=0
。
第二步：扫描每条有向边
e(u, v)
（起点为u，终点为v，下同），其权值为
w(u, v)
。如果
len[u] + w(u, v) < len[v]
，则更新
len[v] = len[u] + w(u, v)
。这一步，总共要重复V-1次，V为顶点总个数。
第三步：扫描每条边
e(u, v)
，其权值为
w(u, v)
。如果存在一条边
e(u, v)
使得
len[u] + w(u, v) < len[v]
，则表明图中存在负权环，最短路径不存在。否则，len数组的元素
len[i]
就是s到i的最短路径长度。
是不是比迪杰斯特拉算法简单的多？而且，从算法的第二、三步可知，图不需要存储邻接表，只需要存储边集即可。所以，我们只需要定义这样的结构体来表示边：
typedef struct
{
int v1; // 起点
int v2; // 终点
long long weight; // 权值
} edge; // 这是有向边的结构体，
能不能再快点呢？我们第二步一定要重复V-1次吗？当然不是！
我们做更新操作时，可以记录一下是否更新。如果某一趟扫描完所有的边，一次都没有更新，则表明，整个图已经更新到最优状态！不要怀疑，你想，第二步的每次操作都是完全一样的，所以，如果你第k次没有更新，则len数组的状态和第k次之前一样，所以再扫描也是做无用功。因此可以考虑用一个flag做标识，一旦没有更新则break。
给出完整代码：
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
using namespace std;
typedef struct
{
int v1;
int v2;
long long weight;
} edge;
edge edges[1000000];
long long len[100001];
int main() {
int v, e, s, i, j;
bool flag;
scanf("%d %d %d", &v, &e, &s);
for (i = 1; i <= v; i++) len[i] = (long long) INT_MAX;
len[s] = 0LL;
for (i = 0; i < e; i++)
{
scanf("%d %d %lld", &edges[i].v1, &edges[i].v2, &edges[i].weight);
}
for (i = 1; i < v; i++)
{
flag = false;
for (j = 0; j < e; j++)
{
if (edges[j].weight + len[edges[j].v1] < len[edges[j].v2])
{
len[edges[j].v2] = edges[j].weight + len[edges[j].v1];
flag = true;
}
}
if (!flag) break; // 未更新则break
}
for (i = 0; i < e; i++)
{ // 检查负权环
if (edges[i].weight + len[edges[i].v1] < len[edges[i].v2])
{
printf("Has negative loop!");
exit(0);
}
}
for (i = 1; i <= v; i++) printf("%lld ", len[i]);
return 0;
}
四、算法效率分析
时间复杂度：最坏 O ( V E ) O(VE) O(VE)，最好 O ( E ) O(E) O(E)，平均 O ( V E ) O(VE) O(VE)。
额外空间： O ( 1 ) O(1) O(1)。存储边： O ( E ) O(E) O(E)。
为什么时间复杂度如此之高呢？因为我们在第二步更新操作时，有些更新是没用的。比如下面这个图：
如果是从E开始更新，边按照ED，DC，CB，BA的顺序，则需要更新4趟才能完成。但是，如果按AB，BC，CD，DA的顺序，则只需更新1趟即可。为了优化这样的效率，还有一个基于bellman-ford的快速算法，叫做SPFA（shortest path fast algorithm）。我们下一节讲这个。