bellman_ford(queue)

在加入隊列的過程可以有一個優化，用visited數組記錄已經在隊列裏的元素，已經在隊列的元素不用重複加入.

#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>
using namespace std;

struct Edge { //鄰接表
    int to;  // 鏈接的節點
    int val; // 邊的權重

    Edge(int t, int w): to(t), val(w) {}  // 構造函數
};


int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<list<Edge>> grid(n + 1); 

    vector<bool> isInQueue(n + 1); // 加入優化，已經在隊裏裏的元素不用重複添加

    // 將所有邊保存起來
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，權值為 val
        grid[p1].push_back(Edge(p2, val));
    }
    int start = 1;  // 起點
    int end = n;    // 終點

    vector<int> minDist(n + 1 , INT_MAX);
    minDist[start] = 0;

    queue<int> que;
    que.push(start); 

    while (!que.empty()) {

        int node = que.front(); que.pop();
        isInQueue[node] = false; // 從隊列裏取出的時候，要取消標記，我們只保證已經在隊列裏的元素不用重複加入
        for (Edge edge : grid[node]) {
            int from = node;
            int to = edge.to;
            int value = edge.val;
            if (minDist[to] > minDist[from] + value) { // 開始鬆弛
                minDist[to] = minDist[from] + value; 
                if (isInQueue[to] == false) { // 已經在隊列裏的元素不用重複添加
                    que.push(to);
                    isInQueue[to] = true;
                }
            }
        }

    }
    if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到達終點
    else cout << minDist[end] << endl; // 到達終點最短路徑
}

bellman_ford負權迴路

在沒有負權迴路的圖中，鬆弛 n 次以上 ，結果不會有變化。

但本題有 負權迴路，如果鬆弛 n 次，結果就會有變化了，因為 有負權迴路 就是可以無限最短路徑（一直繞圈，就可以一直得到無限小的最短距離）。

那麼每鬆弛一次，都會更新最短路徑，所以結果會一直有變化。

#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;

int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid;

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        // p1 指向 p2，權值為 val
        grid.push_back({p1, p2, val});

    }
    int start = 1;  // 起點
    int end = n;    // 終點

    vector<int> minDist(n + 1 , INT_MAX);
    minDist[start] = 0;
    bool flag = false;
    for (int i = 1; i <= n; i++) { // 這裏我們鬆弛n次，最後一次判斷負權迴路
        for (vector<int> &side : grid) {
            int from = side[0];
            int to = side[1];
            int price = side[2];
            if (i < n) {
                if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) minDist[to] = minDist[from] + price;
            } else { // 多加一次鬆弛判斷負權迴路
                if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) flag = true;

            }
        }

    }

    if (flag) cout << "circle" << endl;
    else if (minDist[end] == INT_MAX) {
        cout << "unconnected" << endl;
    } else {
        cout << minDist[end] << endl;
    }
}

單源有限最短路

對所有邊鬆弛一次，相當於計算 起點到達 與起點一條邊相連的節點 的最短距離，那麼對所有邊鬆弛 k + 1次，就是求 起點到達 與起點k + 1條邊相連的節點的 最短距離。

理論上來説，對所有邊鬆弛一次，相當於計算 起點到達 與起點一條邊相連的節點 的最短距離。

對所有邊鬆弛兩次，相當於計算 起點到達 與起點兩條邊相連的節點的最短距離。

對所有邊鬆弛三次，以此類推。

// 版本二
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;

int main() {
    int src, dst,k ,p1, p2, val ,m , n;
    
    cin >> n >> m;

    vector<vector<int>> grid;

    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid.push_back({p1, p2, val});
    }

    cin >> src >> dst >> k;

    vector<int> minDist(n + 1 , INT_MAX);
    minDist[src] = 0;
    vector<int> minDist_copy(n + 1); // 用來記錄上一次遍歷的結果
    for (int i = 1; i <= k + 1; i++) {
        minDist_copy = minDist; // 獲取上一次計算的結果
        for (vector<int> &side : grid) {
            int from = side[0];
            int to = side[1];
            int price = side[2];
            // 注意使用 minDist_copy 來計算 minDist 
            if (minDist_copy[from] != INT_MAX && minDist[to] > minDist_copy[from] + price) {  
                minDist[to] = minDist_copy[from] + price;
            }
        }
    }
    if (minDist[dst] == INT_MAX) cout << "unreachable" << endl; // 不能到達終點
    else cout << minDist[dst] << endl; // 到達終點最短路徑

}