一、无论Floyd还是Dijkstra,算法的假设前提就是,没有负权边。
但是Bellman-Ford算法可以:
if( dis[v[i]] > dis[u[i]] + w[i])
dis[v[i]] = dis[u[i]] + w[i];
u[i], v[i], w[i] 分别记录一条边的起点,终点,边长;dis[x] 表示源点 1 到 顶点 x 的最短距离;
那么算法的意思就是:如果通过顶点 u[i] 使得 源点 1 到 顶点 v[i] 的距离变短,那么执行Dijkstra的“松弛“操作!
过程:
1.先按照给定边的顺序松弛,这时表示的是源点 1 ,只能经过一条边时,到达其他各点的最短路径;
2.重复松弛,这时表示的是源点 1 ,经过 2<= k <= n-2 条边时(n个节点之间最多n-1条边,仅需松弛循环n-2次),可到达其他各点的最短路径;
3.k>=n的可能性(回路):如果是正权回路,那么越走越远;如果是负权回路,则没有最短路径。所以不可能有最短路径中不可能有回路;
二、code
int main(){
int i,j,n,m;
int dis[10];
int inf=999999;
int u[10],v[10],w[10];
scanf("%d %d",&n,&m); //n=点数,m=边数
for(i=1;i<=m;i++){
scanf("%d %d %d",&u[i],&v[i],&w[i]);
}
for(i=1;i<=n;i++)
dis[i]=inf;
dis[1]=0;
for(i=1;i<=n-1;i++){ //Bellman-Ford 算法核心
for(j=1;j<=m;j++){ //松弛的对象是边,不是点!
if(dis[v[j]] > dis[u[j]] + w[j])
dis[v[j]] = dis[u[j]] + w[j];
}
}
//如果n-1轮松弛之后,最短路径依然会发生变化,说明该图存在负权回路!
for(i=1;i<=m;i++)
if(dis[v[i]] > dis[u[i]] + w[i])
printf("图中存在负权回路");
for(i=1;i<=n;i++)
printf("%d\t",dis[i]);
getchar();getchar();return 0;
}
算法的时间复杂度为O(NM),对于稀疏图来说,比Dijkstra要高效的多!