Bellman-Ford + SPFA優化

TIPS

對每一個點都進行過鬆弛操作
最多進行 V-1 次
(超過 V-1 )次代表有負環 WHY? 因為如果兩點之間經過的點大於 V-1 一定有點走過兩次了

什麼是鬆弛?

點的最短路徑被更新的這個動作

SPFA優化?

用 queue -> 簡單來說 就是讓遍歷有依據了
只會 push 可以鬆弛 且 不在 queue 裡面的點

pseudocode:

while queue not empty:
    int t = queue.pop();
    inqueue[t] = false; 
    for(v t的連接點):
        if(v可進行鬆弛):
            更新路徑;
            if(連接點不在queue內):
                push進去;
                inqueue[v] = true;

---

相關題目

UVA 558
(基本題 就是找負環):

#include "bits/stdc++.h"
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
int main() {

    int kase;
    cin >> kase;
    while (kase--) {
        int v, e;
        cin >> v >> e;
        vector<vector<pair<int, int>>> gp(v);
        while (e--) {
            int start, end, w;
            cin >> start >> end >> w;
            gp[start].push_back({end, w});
        }
        queue<int> spfa;
        int vst[v] = {}, dist[v];
        memset(dist, inf, sizeof(dist));
        bool inqueue[v] = {}, flag = true;
        dist[0] = 0;
        spfa.push(0);
        while (!spfa.empty()) {
            int tmp = spfa.front();
            spfa.pop();
            vst[tmp]++;
            if (vst[tmp] > V) {
                flag = 0;
                break;
            }
            inqueue[tmp] = false;
            for (auto ele : gp[tmp]) {
                if (ele.second + dist[tmp] < dist[ele.first]) {
                    dist[ele.first] = ele.second + dist[tmp];
                    if (!inqueue[ele.first]) {
                        spfa.push(ele.first);
                        inqueue[ele.first] = true;
                    }
                }
            }
        }
        if (flag)
            cout << "not possible\n";
        else
            cout << "possible\n";
    }

    return 0;
}