bellman-ford算法

编程与算法

以前说的都是不存在负环的最短路径算法，但是如果一旦边的权值出现负数，则循环将无限进行。所以我们需要一种算法来判断是否出现负环。

下面就简单介绍一下Bellman-ford 算法。

主要思想

求某点到其他点的最短路径，如果经过一条边n-1次后，再次进过还可以减小路径的权值，则说明存在负环。

原文是这样的。

Bellman-ford算法是求含负权图的单源最短路径算法，效率很低，但代码很容易写。即进行持续地松弛，每次松弛把每条边都更新一下，若n-1次松弛后还能更新，则说明图中有负环，无法得出结果，否则就成功完成。

算法简介

  • 首先确定一个源点（起始点），然后定义dis[N]表示源点到其他点的距离。还有定义一个边集。
  • 使用两个循环来对边集中各个边进行一次松弛操作。
  • 循环结束后查看是否还可以进行松弛，如果仍然可以，则存在负环。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct Edge{
	int v,u;
	int w;
}edge[M+1];
bool bellman_ford(int st){  
    for(int i = 1; i <= N; ++i)
        dis[i] = INF;
	dis[st] = 0;
    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].w){  
                dis[edge[j].v] = dis[edge[j].u] + edge[j].w;
            }  
    bool flag = 1;
    for(int i = 1; i <= edgenum; ++i)  
    	if(dis[edge[i].v] > dis[edge[i].u] + edge[i].w)  {
			flag = 0;  
			break;
		}  
	return flag;  
}

补充一下

对于这个算法，说的有点简略，不过仔细琢磨一下代码，也就懂了。啊哈哈哈哈。