浅谈最短路径O（VE）好用的无优化算法算法+《热浪》题解——————《最短路径·O(VE)Bell MEN-FORD篇》
浅谈最短路径O（VE）好用的无优化算法算法——————《最短路径·O(VE)Bell MEN-FORD篇》
Bellman-Ford算法
注意：Dijk不能处理负边权。
Bellman-Ford 和 Spfa常用来处理负边权,当然Floyd也可以。但比较慢
Bellman-Ford算法能在更普遍的情况下（存在负权边）解决单源点最短路径问题。对于给定的带权（有向或无向）图 G=（V,E），其源点为s，加权函数 w 是边集 E 的映射。对图G运行Bellman-Ford算法的结果是一个布尔值，表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路，算法将给出从源点s到图G的任意顶点v的最短路径d[v]。
Bellman-Ford算法流程分为三个阶段：
（1）初始化：将除源点外的所有顶点的最短距离估计值 d[v] ←+, d[s] ←0;
（2）迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）
（3）检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。
适用条件和范围：
1.单源最短路径(从源点s到其它所有顶点v);
2.有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);
3.边权可正可负(如有负权回路输出错误提示);
4.差分约束系统;
以上丄丄丄都是看不懂的废话，
———————————华丽的分割线————————————
言归正传
贴道题目更好理解：
最短路径专题】热浪 (Standard IO)
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
题目描述
德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John 此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。
FJ 已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过 T (1 <= T <= 2,500)个城镇，方便地标号為 1 到 T。除了起点和终点外的每个城镇由两条双向道路连向至少两个其它的城镇。每条道路有一个通过费用（包括油费，
过路费等等）。
给定一个地图，包含 C (1 <= C <= 6,200)条直接连接 2 个城镇的道路。每条道路由道路的起点 Rs，终点 Re (1 <= Rs <= T; 1 <= Re <= T)，和花费(1 <= Ci <= 1,000)组成。求从起始的城镇 Ts (1 <= Ts <= T)到终点的城镇 Te(1 <= Te <= T)最小的总费用。
输入
第一行: 4 个由空格隔开的整数: T, C, Ts, Te
第 2 到第 C+1 行: 第 i+1 行描述第 i 条道路。有 3 个由空格隔开的整数:Rs, Re 和 Ci
输出
一个单独的整数表示从 Ts 到 Te 的最小总费用。数据保证至少存在一条道路。
样例输入
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
样例输出
7
看到这道题大家应该觉得Floyd不可以做。对没错因为Floyd是多元最短路。那有没有更好更快的算法呢，答案是：当然有呀，我都问到这了可能没有嘛？
但我们的时间复杂度只用O(VE），（V为点数，E为边数）相当于O（n^2）做法，少了一个循环WOW！但思想仍然是一样的。好我们分析一下，当读入完之后，把所有的城镇都赋上一个特殊值，最好是最大值。然后枚举除自己当前城市的所有城市，然后枚举路径关系。
重点：中间两个IF主要是，我们要更新这个点，就看一下与它连通的其他点，能否以更小的值更新它的最短路，即可。最后还得判一下在本次循环中是否被更新，如被更新即可Break。
附上Pascal AC代码：
var
n,m,x,y,i,j,bj:longint;
a,b,c,dis:array[-10005..1000005] of longint;
begin
readln(n,m,x,y);
for i:=1 to m do
readln(a[i],b[i],c[i]);
for i:=1 to n do
dis[i]:=maxlongint div 2;
dis[x]:=0;
for i:=1 to n-1 do
begin
bj:=0;
for j:=1 to m do
begin
if dis[b[j]]>dis[a[j]]+c[j] then
begin
dis[b[j]]:=dis[a[j]]+c[j];
bj:=1;
end;
if dis[a[j]]>dis[b[j]]+c[j] then
begin
dis[a[j]]:=dis[b[j]]+c[j];
bj:=1;
end;
end;
if bj=0 then
break;
end;
writeln(dis[y]);
end.
附上C++ AC 代码:
#include <cstdio>
#include <iostream>
using namespace std;
bool bj;
int n,m,x,y,i,j,a[1000005],b[1000005],c[1000005],dis[1000005];
int main()
{
scanf("%d%d%d%d",&n,&m,&x,&y);
for (i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i],&b[i],&c[i]);
}
for (i=1;i<=n;i++)
{
dis[i]=100000005;
}
dis[x]=0;
for (i=1;i<=(n-1);i++)
{
bj=false;
for (j=1;j<=m;j++)
{
if (dis[b[j]]>dis[a[j]]+c[j])
{
dis[b[j]]=dis[a[j]]+c[j];
bj=true;
}
if (dis[a[j]]>dis[b[j]]+c[j])
{
dis[a[j]]=dis[b[j]]+c[j];
bj=true;
}
}
if (bj==false)
{
break;
}
}
printf("%d",dis[y]);
return 0;
}
请看下集预告：SPFA，O(KE)算法。