No.6.3 最短路径之Bellman-Ford算法--解决负权边
一、无论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的可能性（回路）：如果是正权回路，那么越走越远；如果是负权回路，则没有最短路径。所以不可能有最短路径中不可能有回路；
< 问：这叫解决了负权回路？
其实呢，它也没有“解决”掉负权回路，只不过不同之处在于：Floyd算法会因为负权边的存在，使得已经计算出来的最短路径可能是错误的；Dijkstra算法完全拿负权边没办法，因为负权边的引入已经破坏了算法的假设基础（距离已知点的路径最短的点，为下一次执行的基础）；Bellman算法先确定一个起始源点，由这个确定的源点判断点间距，解耦了源点与其他各点之间的不确定性，同时可以在超出预定循环次数的情况下，发现负权回路问题；
简单点说，Floyd虽然可以计算最短路径（值不一定准确，但是因为所有点均摊了负权边，最小路径还是可以找到的），但是时间复杂度太高，适用于小数据点量的所有点之间的最短路径；Dijkstra算法，点和点之间依赖性太强，所以引入负权边时，导致之前已经确定的点变为可能的不确定点；Bellman则直接确定一个源点，由这个源点驱动其他点，解决了负权边的不确定性！
>
二、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要高效的多！
三、Bellman算法的简单优化：事实上，很多时候循环只进行了不到n-1次就完成了所有边的松弛操作。
int main(){
int i,j,k,n,m;
int dis[10],res[10];
int flag;
int inf=999999;
int u[10],v[10],w[10];
scanf("%d %d",&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++){
flag=1;
for(k=1;k<=n;k++) res[k]=dis[k]; //边松弛之前，做好备份；
for(j=1;j<=m;j++){
if(dis[v[j]] > dis[u[j]] + w[j])
dis[v[j]] = dis[u[j]] + w[j];
}
for(k=1;k<=n;k++) //松弛之后，对比两个dis数组，如果数组发生变化，关闭flag；否则说明无需继续，flag继续为1，可以跳出Bellman算法循环
if(res[k]!=dis[k])
{
flag=0;
break;
}
if(flag==1) break;
}
for(i=1;i<=m;i++) //Bellman算法循环完成之后，如果还可以继续优化路径，说明图中有负权回路，不存在最短路径！
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(N*（N+M)），介于Dijkstra和Bellman之间，但是考虑到实际情况下的稀疏图，以及两点之间的边更加简单性，这种优化算法更加实用！
四、Bellman-Ford队列优化
前面的Floyd、Dijkstra、Bellman用了贪婪算法，即给一个点、一条边之后，要对全部边做松弛。这似乎是一种浪费！
一种优化思路：每次仅对最短路径发生变化的点的相邻边做松弛（类似广度优先算法：先找到相邻最近点，再驱动次一级的点）！
int main(){
int inf=999999;
int i,j,k,n,m;
int que[100],head=1,tail=1; // 队列+book[]，广度优先算法必备品
int dis[10],u[10],v[10],w[10]; //邻接表存储图
int first[10],next[10],book[10];
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
scanf("%d %d %d",&u[i],&v[i],&w[i]);
for(i=1;i<=n;i++) //以点为基准的初始化
{
first[i]=-1;
dis[i]=inf;
book[i]=0;
}
dis[1]=0;
for(i=1;i<=n;i++){
next[i]=first[u[i]];
first[u[i]] = i;
}
que[tail]=1;
tail++;
book[1]=1;
while(head
/*if(k==-1){ //因为是以确定点为驱动，只有以该点为入向的最短路径变化了，才会驱动以该点为出向的其他点，所以k==-1的只有入向点，没有可供其驱动的下一级点集
for(j=1;j<=m;j++){
if(dis[v[j]] > dis[u[j]]+w[j]){
dis[v[j]] = dis[u[j]]+w[j];
if(book[v[j]]==0){
que[tail]=v[j];
tail++;
book[v[j]]=1;
}
}
}
continue;
}*/
while(k!=-1){
if(dis[v[k]] > dis[u[k]]+w[k]){
dis[v[k]] = dis[u[k]]+w[k];
if(book[v[k]]==0){ //只有不在队列中的点才能入队
que[tail]=v[k];
tail++;
book[v[k]]=1;
}
}
k=next[k]; //邻接表遍历
}
book[que[head]]=0; //队首的点出队之后，有可能被后续的点集再次驱动
head++;
}
printf("\n");
for(i=1;i<=n;i++)
printf("%d\t",dis[i]);
getchar();getchar();return 0;
}
1.目的：当一个顶点的入向最短路程变小后，需要对其所有出向边进行松弛队列优化Bellman-Ford算法，最坏的情况下时间2.复杂度为O(NM)，即每个点的入队，都会引起所有点的最短路径变小！
3.如果某个点进入队列的次数超过n次（点集总数），那么这个图存在负权环！