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 0

Sample 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;
}