最短路 | Ray's Blog

Bellman-Ford

Bellman-Ford 可以在有負邊的圖 （不論有向無向）上找出單源最短路，還可以偵測負環。在最短路存在的情況下，由於每次鬆弛最少會使最短路的邊數$+1$，而最短路的邊數最多為 $n - 1$ （每個節點最多經過一次），因此最多進行 $n - 1$ 次鬆弛操作。若到了第 $n$ 次迴圈還可以繼續鬆弛，則代表該圖存在負環。

所以偵測負環的方式就是在第 $n$ 次迴圈檢測還能不能鬆弛，時間複雜度為 $O(nm)$。

負環判斷常見誤區

以 $s$ 為源點執行 Bellman-Ford 若給出沒有負環的結果時，只能表示從 $s$ 出發不能抵達負環，而不代表圖上不存在負環。

因此若要判斷整張圖上存不存在負環，可以建立一個超級源點，向圖上每個點連接一條邊權為 $0$ 的邊，然後以此為起點執行 Bellman-Ford。

實現

int n, m;
struct {
	int u, v, w;
} edges[MAXM];
ll dis[MAXN];

bool bellman(int s) {
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	
	for (int i = 0; i < n; i++) {
		for (auto const& [u, v, w] : edges) {
		    if (dis[u] == dis[0]) continue; // INF + c = INF
		    if (dis[v] > dis[u] + w) {
		        dis[v] = dis[u] + w;
		    }
		}
	}
	
	for (auto const& [u, v, w] : edges) {
	    if (dis[u] == dis[0]) continue; // INF + c = INF
	    if (dis[v] > dis[u] + w) return true;
	}
	return false;
}

實作常見誤區

在更新距離時，要注意設定為 $+\infty$ 的節點。 Bellman-Ford 裡面無限大加減常數仍為無限大，所以要對距離為 $+\infty$ 的點做特判。

SPFA

SPFA （Shortest Path Faster Algorithm）的想法是，只有在上一輪鬆弛過的節點，所連接的邊才有可能引起下一次鬆弛的操作。那麼就可以用隊列來維護「哪些節點會引起鬆弛操作」，大大加快執行速度。

SPFA 已死

雖然多數情況下 SPFA 比較快，但是主辦方還是能夠容易的將 SPFA 卡成 $O(nm)$ ，所以我覺得全用 Bellman-Ford 就好。

int n, m;
vector<pii> mat[MAXN];
ll dis[MAXN];
int inq[MAXN], cnt[MAXN];

bool spfa(int s) {
	memset(dis, 0x3f, sizeof(dis));
	
	queue<int> q;
	dis[s] = 0;
	inq[s] = 1;
	q.push(s);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		inq[u] = 0;
		for (auto const& [v, w] : mat[u]) {
			if (dis[v] <= dis[u] + w) continue;
			dis[v] = dis[u] + w;
			cnt[v] = cnt[u] + 1;
			if (cnt[v] >= n) return true;
			if (!inq[v]) {
			    inq[v] = 1;
			    q.push(v);
			}
		}
	}
	return false;
}

找出最短路

開一個 $pre$ 陣列，在鬆弛時紀錄是從哪個節點轉移過去的，結束時再暫存結果遞迴回到原點，然後反著輸出回去。

int n, m;
struct {
	int u, v, w;
} edges[MAXM];
ll dis[MAXN];
int pre[MAXN];

bool bellman(int s) {
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	pre[s] = s;
	
	for (int i = 0; i < n; i++) {
		for (auto const& [u, v, w] : edges) {
		    if (dis[u] == dis[0]) continue;
		    if (dis[v] > dis[u] + w) {
		        dis[v] = dis[u] + w;
		        pre[v] = u;
		    }
		}
	}
	
	for (auto const& [u, v, w] : edges) {
	    if (dis[u] == dis[0]) continue;
	    if (dis[v] > dis[u] + w) return true;
	}
	
	return false;
}

int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    for (int i = 0; i < m; i++)
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    
    bool res = bellman(s);
    if (res) {
        cout << "NO\n";
    } else {
        cout << "YES" << "\n";
        cout << dis[t] << "\n";
		
        vector<int> ans;
        ans.reserve(MAXN);
		
		int x = t;
        while (true) {
	        ans.push_back(x);
            x = pre[x];
            if (x == s) break;
        }
	    ans.push_back(s);
		
		reverse(ans.begin(), ans.end());
		for (int v : ans) cout << v << " ";
		cout << "\n";
    }
}

找出任意負環

在第 $n$ 次迴圈時，鬆弛 $dis$ 所找到的邊上兩點 $(u, v)$ 其實不必然存在於負環中，這兩點可以都在負環外，只是受負環的影響仍可繼續鬆弛。

一樣是開一個 $pre$ 陣列記錄轉移節點，然後在第 $n$ 次鬆弛時紀錄仍可被更新的任意節點 $x$ 。接著從 $x$ 開始沿著 $pre$ 跑 $n$ 步。這樣做的用意是，由於最短路最多有 $n - 1$ 條邊，往回跑 $n$ 步可以確保回到任一個負環中。

接下來從上一步結束的節點沿著 $pre$ 走，並記錄走過的節點，直到走回起點為止。

int n, m;
struct {
	int u, v, w;
} edges[MAXM + MAXN];
ll dis[MAXN];
int pre[MAXN];

int bellman(int s) {
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	pre[s] = s;
	
	for (int i = 0; i < n; i++) {
		for (auto const& [u, v, w] : edges) {
		    if (dis[u] == dis[0]) continue;
		    if (dis[v] > dis[u] + w) {
		        dis[v] = dis[u] + w;
		        pre[v] = u;
		    }
		}
	}
	
	int x = 0;
	for (auto const& [u, v, w] : edges) {
	    if (dis[u] == dis[0]) continue;
	    if (dis[v] > dis[u] + w) {
	        pre[v] = u;
	        x = u;
	    }
	}
	
	return x;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    for (int i = m; i < n + m; i++)
        edges[i] = {MAXN - 1, i - m + 1, 0}; // 建立超級源點
    
    int x = bellman(MAXN - 1);
    if (x) {
        cout << "YES\n";
        for (int i = 1; i <= n; i++) x = pre[x];
		
		vector<int> ans;
		ans.reserve(MAXN);
		int s = x;
		while (true) {
			ans.push_back(x);
			x = pre[x];
			if (x == s) break;
		}
		ans.push_back(s);
		
		reverse(ans.begin(), ans.end());
		for (int v : ans) {
			cout << v << " ";	
		}
		cout << "\n";
    } else {
        cout << "NO\n";
    }
}

Dijkstra

Dijkstra 可以在無負邊的圖 （不論有向無向）上找出單源最短路，在 $m = O(n)$ 的圖上有 $O(m\log n)$ （使用 std::priority_queue ），在 $m = O(n^2)$ 的圖上有 $O(n^2)$ 。

實現

std::priority_queue 實現：

ll dis[MAXN];
int vis[MAXN];
vector<pii> mat[MAXN];

void dijkstra(int s) {
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	
	priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({s, 0});
    
    while (!pq.empty()) {
        pii curr = pq.top();
        pq.pop();
        
        int u = curr.second;
        if (vis[u]) continue;
        vis[u] = 1;
        
        for (int v : mat[u]) {
            if (dis[v] > dis[u] + w) {
	            dis[v] = dis[u] + w;
	            pq.push({dis[v], v});
            }
        }
    }
}

稠密圖實現：

ll dis[MAXN];
int vis[MAXN];
vector<pii> mat[MAXN];

void dijkstra(int s) {
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
    
    for (int i = 1; i <= n; i++) { // 最多n次鬆弛
	    int u = 0;
	    ll mdis = dis[0];
	    for (int j = 1; j <= n; j++) {
		    if (!vis[j] && dis[j] < mdis) {
			    mdis = dis[j];
			    u = j;
		    }
	    }
	    
	    vis[u] = 1;
	    for (int v : mat[u]) {
	        dis[v] = min(dis[v], dis[u] + w);
	    }
    }
}

Bellman-Ford#

實現#

SPFA#

找出最短路#

找出任意負環#

Dijkstra#

實現#

Bellman-Ford

實現

SPFA

找出最短路

找出任意負環

Dijkstra

實現