算法導論 ch24 單源最短路徑 Bellman-Ford

基本算法實作如下，

/home/a/j/nomad2:cat bellman.CPP 
#include <iostream>
using namespace std;

typedef int typec;
const typec inf = 0x3f3f3f3f;
const int V = 10, E = 20;
int n, m, pre[V], edge[E][3];

typec dist[V];

int relax(int u, int v, typec c) {
        if (dist[v] > dist[u] + c) {
                dist[v] = dist[u] + c;
                pre[v] = u;
                return 1;
        }
        return 0;
}

int bellman(int src) {
        int i, j;
        for (i = 0; i < n; i++) {
                dist[i] = inf;
                pre[i] = -1;
        }
        dist[src] = 0;
        bool flag;

        for (i = 1; i < n; i++) {
                flag = false;
                for (j = 0; j < m; j++) {
                        if (1 == relax(edge[j][0], edge[j][1], edge[j][2])) {
                                flag = true;
                        }
                }
                if (!flag) {
                        break;
                }
        }
        for (j = 0; j < m; j++) {
                if (1 == relax(edge[j][0], edge[j][1], edge[j][2])) {
                        return 0;
                }
        }
        return 1;
}

void input() {
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
                cin >> edge[i][0] >> edge[i][1] >> edge[i][2];
        }
}

void display() {
        for (int i = 0; i < n; i++) {
                cout << dist[i] << " ";
        }
        cout << endl;
        for (int i = 0; i < n; i++) {
                cout << pre[i] << " ";
        }
        cout << endl;
}

int main() {
        input();
        bellman(0);
        display();
        return 0;
}
           

測試用例為書上的圖24-4，

/home/a/j/nomad2:cat input
5 10
0 1 6
0 3 7
1 2 5
1 3 8
1 4 -4
2 1 -2
3 2 -3
3 4 9
4 0 2
4 2 7
/home/a/j/nomad2:cat input|./a.out 
0 2 4 7 -2 
-1 2 3 0 1 
           

優化：SPFA(Shortest-Path Faster Algoithm)，參考：

http://hi.baidu.com/jzlikewei/blog/item/94db7950f96f995a1038c2cd.html

http://hi.baidu.com/jzlikewei/blog/item/5343d134b54c6f48251f14cd.html

POJ

From: http://hi.baidu.com/sunshine_0316/blog/item/36f4c7a3d9113aaacaefd055.html

三、 學以緻用

POJ 1201 Intervals 差分限制系統

設S(i)為 0..i-1 中在最終序列中的的整數個數。則限制條件如下:

S(b)-S(a) >= c

0 <= S(i+1) - S(i) <= 1 <==> S(i+1)-S(i) >= 0;

S(i)-S(i+1) >= -1

注意本題要求的是最小值, 而按照>=号建圖後發現圖中有負環, 怎麼辦呢?

其實很簡單, 本題求的不是最短路, 而是最長路! Bellman_ford即可!

POJ 1275 Cashier Employment 出納員的雇傭

黑書上有詳細講解

POJ 1364 King 差分限制系統

這個題目構圖之後, 隻需要用bellman_ford判斷是否有負圈.

構圖方法:

首先進行轉換:a[j]+...+a[j+m] = a[1]+...a[j+m] - (a[1]+...+a[j-1]) = sum[j+m] -

sum[j-1] >(<) ki. 差分限制隻能全部是<=或者(>=).

第二步轉換: sum[j+m]-sum[j-1] <= ki-1 或者 sum[j-1]-sum[j+m] <= -ki-1.

限制圖構造好後就是簡單的Bellman-Ford了!

POJ 1716 Integer Intervals 是1201的簡單版本, 貪心算法能夠得到更好的效果.

POJ 2983 Is the Information Reliable?

差分限制題, 處理一下等号的情況, 然後普通的Bellman_ford

POJ 3159 Candies 最短路徑

Bellman-Ford逾時, Dijkstra算法可以高效解決, SPFA(隊列)居然逾時...SPFA修改為堆棧實作就過了.

POJ 3169 Layout 差分限制

Bellman-Ford 和 SPFA 實作均可

POJ 3259 Wormholes 判斷負權回路

TOJ 2976 Path 單純的最短路徑 可練習SPFA

ZOJ 3033 Board Games 首先，DFS判斷可達性，不可達直接輸出infinity結束，可達，bellman-ford判斷是否存在負環，存在輸出infinity，否則，輸出最短距離。