适用于解决单源最短路问题,即固定一个起点,求它到其他所有点的最短路的问题。
本质思想为dp。
记从起点s出发到顶点i的最短距离为d[i]。
则有d[i]=min{d[j]+从j直接到i边的距离}
那么我们只要初始化d[s]=0,d[i]=INF,再不断使用这条递推关系式更新d[i]。只要图中没有负圈,这样的更新操作一定是有限的。结束之后的d[i]就是最短距离了。
初始化
建图的时候 e.cost 先全设为INF(表示两点之间没有路)
dp前 d[v]先全设为INF,d[源点]=0;
还原路径时 pre[v]可以全设为-1,方便路径还原
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
struct edge
{
int from,to,cost;
};
edge es[MAX_E];
int d[MAX_V],pre[MAX_V],path[MAX_V];
int V,E;//v顶点数 E边数
int Bellman-Ford(int s)
{ memset(pre,-1,sizeof(pre));
memset(d,0x3f,sizeof(d));
d[s]=0;
for(int i=0;i<V;i++)
{ int flag=0;
for(int j=0;j<E;j++)
{
edge e=es[j];
if(d[e.to]>d[e.from]+e.cost)
{
d[e.to]=d[e.from]+e.cost;
pre[e.to]=e.from;
flag=1;
}
if(i==v-1&&flag==1) return -1;//如果第v次更新了,则存在负圈
if(flag==0) return 1;//flag=0 此次没更新,表示更新已经结束,直接退出
}
}
}
void getpath(int t) //还原路径
{
int i;
for( i=0;i<=n;i++)
{ path[i]=t;
t=pre[t];
if(t==-1) break;
}
reverse(path,path+i);
}
|
这里解释一下为什么外循环至多只要执行v-1次。
如果在图中没有负圈,那么任何一条最短路径都不会经过同一个顶点两次(也就是说,最多通过v-1条边)
对于外循环而言,最差的情况(即线路是从D->C->B->A倒着给的)每次也能更新一条边,所以最多只要循环v-1次。
因此Bellman-Ford算法的复杂度为O(V*E),而且可以适用于存在负边的情况。