Bellman-Ford算法可以处理负权边的最短路问题。
下面以HDU2544为例子，展示代码。
在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？
Input
输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。0
输入保证至少存在1条商店到赛场的路线。Output
对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间
Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0Sample Output
3
2
一、Bell-Ford 邻接矩阵
// Bellman-Ford 邻接矩阵
#include <bits/stdc++.h>
using namespace std;
const int maxn = 510;
const int INF = 0x3fffffff;
int g[maxn][maxn], n, m, d[maxn];
int Bellman(int s, int t){
for(int i=1; i<=n; i++)
d[i] = INF;
d[s] = 0;
for(int k=1; k<n; k++){ // n-1轮松弛
for(int i=1; i<=n; i++){ // 遍历所有的边，看能否松弛
if(d[i] < INF){ // 可以从这里松弛
for(int j=1; j<=n; j++) // 找可以松弛的边
if(g[i][j] < INF && d[j] > d[i]+g[i][j])
d[j] = d[i] + g[i][j];
}
}
}
for(int i=1; i<=n; i++){ // 判定负环
if(d[i] < INF){ // 可以从这里松弛
for(int j=1; j<=n; j++)
if(g[i][j] < INF && d[j] > d[i]+g[i][j]) // 有负环
return -INF;
}
}
return d[t];
}
int main(){
while(~scanf("%d %d", &n, &m)){
if(n==0 && m==0)
break;
int u, v, w;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++)
g[i][j] = INF;
g[i][i] = 0;
}
for(int i=1; i<=m; i++){
scanf("%d %d %d", &u, &v, &w);
g[u][v] = g[v][u] = min(g[u][v], w); // 无向边
}
printf("%d\n", Bellman(1, n));
}
return 0;
}
二、Bell-Ford 邻接表
完全按照算法步骤进行的模版代码。
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;
const int maxn = 110;
struct Edge{
int from, to, dist;
Edge(int f, int t, int d): from(f), to(t), dist(d) {}
};
vector<Edge> edge; // 存边
vector<int> G[maxn]; // 存边的序号
int d[maxn], n, m;
void init(){
for(int i=1; i<=n; i++)
G[i].clear();
edge.clear();
}
int Bellman(int s, int t){
for(int i=1; i<=n; i++)
d[i] = INF;
d[s] = 0;
for(int k=1; k<n; k++){
for(int i=0; i<edge.size(); i++){
Edge e = edge[i];
if(d[e.from] < INF && d[e.to] > d[e.from]+e.dist)
d[e.to] = d[e.from] + e.dist;
}
}
for(int i=1; i<edge.size(); i++){ // 判负环
Edge e = edge[i];
if(d[e.from] < INF && d[e.to] > d[e.from]+e.dist) // 有负环
return -INF;
}
return d[t];
}
int main(){
while(~scanf("%d %d", &n, &m)){
if(n==0 && m==0)
break;
int u, v, w;
init();
for(int i=1; i<=m; i++){
scanf("%d %d %d", &u, &v, &w);
edge.push_back(Edge(u, v, w));
edge.push_back(Edge(v, u, w));
int t = edge.size();
G[u].push_back(t-2);
G[v].push_back(t-1);
}
printf("%d\n", Bellman(1, n));
}
return 0;
}
优化判负环代码，且优化判定松弛轮数，不一定是n-1轮，可能更少。
int Bellman(int s, int t){
for(int i=1; i<=n; i++)
d[i] = INF;
d[s] = 0;
int k = 0;
int cnt = edge.size();
bool update = true;
while(update){ // 上次还有松弛，继续
k ++;
if(k==n){ // 有负环
return -INF;
}
update = false;
for(int i=0; i<cnt; i++){
Edge e = edge[i];
if(d[e.from] < INF && d[e.to] > d[e.from]+e.dist){
d[e.to] = d[e.from] + e.dist;
update = true;
}
}
}
return d[t];
}
三、队列优化SPFA
到这里优化，显然没邻接矩阵什么事情了，肯定是用到邻接表或链式前向星。
优化的原因在于，松弛的时候并不需要遍历所有的边，可以发现能松弛的边，都是来源于它的前驱节点可以被松弛。因此用队列就可以优化。
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;
const int maxn = 110;
struct Edge{
int from, to, dist;
Edge(int f, int t, int d): from(f), to(t), dist(d) {}
};
vector<Edge> edge; // 存边
vector<int> G[maxn]; // 存边的序号
int d[maxn], cnt[maxn], n, m;
queue<int> q;
bool inq[maxn];
void init(){
for(int i=1; i<=n; i++)
G[i].clear();
edge.clear();
}
int SPFA(int s, int t){
for(int i=1; i<=n; i++)
d[i] = INF;
memset(cnt, 0, sizeof(cnt)); //结点入队的次数
memset(inq, false, sizeof(inq));
d[s] = 0;
cnt[s] = 1;
q.push(s);
inq[s] = true;
while(!q.empty()){
int u = q.front();
q.pop();
inq[u] = false;
for(int i=0; i<G[u].size(); i++){
int v = G[u][i]; // 边的序号
Edge e = edge[v]; // 边的信息
if(d[e.to] > d[e.from]+e.dist){ // 可以松弛， e.from=u
d[e.to] = d[e.from] + e.dist;
if(!inq[e.to]){ // 不在队列中
q.push(e.to);
inq[e.to] = true;
cnt[e.to] ++;
if(cnt[e.to]>=n){ // 有负环
return -INF;
}
}
}
}
}
return d[t];
}
int main(){
while(~scanf("%d %d", &n, &m)){
if(n==0 && m==0)
break;
int u, v, w;
init();
for(int i=1; i<=m; i++){
scanf("%d %d %d", &u, &v, &w);
edge.push_back(Edge(u, v, w));
edge.push_back(Edge(v, u, w));
int t = edge.size();
G[u].push_back(t-2);
G[v].push_back(t-1);
}
printf("%d\n", SPFA(1, n));
}
return 0;
}
