1．帶負(fù)權(quán)值邊的有向圖中的最短路徑路徑問(wèn)題
【問(wèn)題描述】
對(duì)于一個(gè)帶負(fù)權(quán)值邊的有向圖敬察，實(shí)現(xiàn)Bellman-Ford算法唱逢，
求出從指定頂點(diǎn)s到其余頂點(diǎn)的最短路徑爷速，并判斷圖中是否存在負(fù)環(huán)陵刹。

例圖

例圖

思路

使用dist[]數(shù)組存放每個(gè)結(jié)點(diǎn)距離起始點(diǎn)的距離，一共進(jìn)行N-1次循環(huán)(因?yàn)橐还灿蠳個(gè)頂點(diǎn)碾盐，最多的路徑也只有N-1條邊)晃跺，每次循環(huán)對(duì)每一條邊進(jìn)行一次update()。
在開(kāi)始bellman-ford前對(duì)所有結(jié)點(diǎn)進(jìn)行初始化,dist[]除了起始點(diǎn)為0其余均為INF毫玖。
每次循環(huán)對(duì)每一條邊進(jìn)行update()掀虎，如果滿(mǎn)足在路徑中加入這條邊更優(yōu)，則進(jìn)行一次更新付枫。
如何判斷負(fù)環(huán)：
如果再進(jìn)行一次結(jié)點(diǎn)遍歷烹玉，有結(jié)點(diǎn)的dist可以更新，則說(shuō)明還沒(méi)有最優(yōu)即存在負(fù)環(huán)阐滩。

代碼實(shí)現(xiàn)

#include <iostream>
#define N 6
#define INF 255
#define NONE -1
using namespace std;

int graph[N][N];
int dist[N];
int prevNode[N];
int START = 0;
bool hasNegCir = false;
void updateEdge(int from, int to) {
    //cout << "邊(" << from << "," << to << ")" << endl;
    if (dist[from] + graph[from][to] < dist[to]) {
        dist[to] = dist[from] + graph[from][to];
        prevNode[to] = from;
        //cout << "dist[" << to << "]更新為" << dist[to] << endl;
    }
}

void setEdge(int from, int to, int weight) {
    graph[from][to] = weight;
}

int getWeight(int from, int to) {
    return graph[from][to];
}

bool isConnected(int from, int to) {
    return graph[from][to]!=INF;
}

void BF() {
    for (int i = 0; i < N; i++) {
        dist[i] = INF;
        prevNode[i] = NONE;
    }
    dist[START] = 0;
    for (int i = 0; i < N - 1; i++) {
        for (int u = 0; u < N; u++) {
            for (int v = 0; v < N; v++) {
                if (isConnected(u,v)) {
                    updateEdge(u, v);
                }
            }
        }
    }

    for (int u = 0; u < N; u++) {
        for (int v = 0; v < N; v++) {
            if (dist[v] > dist[u] + graph[u][v]) {
                cout << "有負(fù)環(huán)" << endl;
                return;
            }
        }
    }
     cout << "無(wú)負(fù)環(huán)" << endl;
}

void printPath(int end) {
    if (end) {
        printPath(prevNode[end]);
        cout << "-->";
    }
    cout << end;
}

int main(void) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            graph[i][j] = INF;
        }
    }
    setEdge(0, 1, 10);
    setEdge(0, 4, 4);
    setEdge(0, 5, 2);
    setEdge(1, 2, -4);
    setEdge(1, 4, 1);
    setEdge(3, 2, 2);
    setEdge(3, 1, -5);
    setEdge(4, 3, 6);
    setEdge(5, 4, 1);
    BF();
    for (int i = 0; i < N; i++) {
        cout << START << "到" << i << "的最短距離" << dist[i] << endl;
        printPath(i);
        cout << endl;
    }
    system("pause");
    return 0;
}

運(yùn)行結(jié)果

運(yùn)行結(jié)果