【圖論】單源最短路

前言

今天，我們來講最短路，首先看只有一個起點（單源）的情況。

為了書寫方便，我們約定以下內容：

template<class W>
using Graph = vector<vector<pair<int, W>>>;  // 鄰接表(vector實現)template<class W>
using AdjMatrix = vector<vector<W>>;   // 鄰接矩陣template<class W>
struct Edge{int u, v;W w;
};

圖的頂點數記為 $n$ ，邊數記為 $m$ 。
最短路的源點記為 $s$ 。
記 $w(u,v)$ 為邊 $(u,v)$ 的權值。
記 $d_u$ 為點 $s$ 到點 $u$ 的實際最短路長度。
記 $dis_u$ 為點 $s$ 到點 $u$ 的估計最短路長度。任何時候都有 $dis_u \ge d_u$ ，特別地，當最短路算法結束時， $dis_u=d_u$ 。

Bellman-Ford 算法

Bellman–Ford 算法是一種基于松弛（relax）操作的最短路算法，可以求出有負權的圖的最短路，并可以對最短路不存在（有負環）的情況進行判斷。

過程

先介紹松弛操作：對于邊 $u\to v$ ，松弛操作對應下式：

$dis_v=min(dis_v,dis_u+w(u,v))$

這么做很容易理解：嘗試用 $s\to u\to v$ （ $s \to u$ 取最短路徑）去更新 $v$ 點最短路的長度，如果這條路徑更優，就進行更新。

我們不斷嘗試對圖上每一條邊進行松弛。每進行一輪循環，就對圖上所有的邊都松弛一遍，當一次循環中沒有成功的松弛操作時，算法停止。

那么，需要循環多少次呢？

如果最短路存在，那么每一次松弛都會讓最短路至少加上一條邊。而一條簡單路徑最多只有 $n-1$ 條邊，所以最多松弛 $n-1$ 輪就能得到最短路。

如果第 $n$ 輪松弛操作仍然成功，那么說明從 $s$ 出發，能到達一個負環。

綜上，時間復雜度為 $O(nm)$

判負環的坑點

需要注意的是，跑Bellman-Ford算法時，如果沒有給出存在負環的結果，那么只能說明從 $s$ 出發不能到達一個負環，不能保證圖上沒有負環（除了連通圖）。

所以，如果需要判斷圖上是否有負環，最嚴謹的做法是建立一個超級源點，向圖上每個節點連一條權值為 $0$ 的邊，然后以超級源點為起點跑 Bellman–Ford。

代碼

說明：返回的pair第一個元素表示圖是否無負環，第二個元素才是最短路數組。

// edge - 邊集
// n - 頂點數
// s - 源點
template<class W>
pair<bool, vector<W>> bellman(const vector<Edge<W>>& edge, int n, int s) {W inf = numeric_limits<W>::max();vector<W> dis(n, inf);dis[s] = 0;bool flag = false;for (int i = 0; i < n; i++) {flag = false;for (auto e : edge) {if (dis[e.u] == inf) continue;if (dis[e.v] > dis[e.u] + e.w) {dis[e.v] = dis[e.u] + e.w;flag = true;}}if (!flag) return make_pair(true, dis);}return make_pair(false, vector<W>());
}

SPFA 算法

即 Shortest Path Faster Algorithm，是對于 Bellman-Ford 的優化。

思路

很多時候，我們不需要那么多無用的松弛操作。

很顯然，只有上一次被松弛的結點，所連接的邊，才有可能引起下一次的松弛操作。

那么我們用隊列來維護哪些結點可能會引起松弛操作，就能只訪問必要的邊了。

如果要判負環，可以設 $cnt_u$ 表示 $s \to u$ 的最短路經過了多少條邊.

當 $cnt_u \ge n$ 時，說明從 $s$ 點出發，可以抵達一個負環。

代碼

// G - 圖
// s - 源點
template<class W>
pair<bool, vector<W>> spfa(const Graph<W>& G, int s) {int n = G.size();W inf = numeric_limits<W>::max();queue<int> q;vector<W> dis(n, inf);vector<int> cnt(n, 0);vector<bool> vis(n, false);q.push(s);dis[s] = 0;vis[s] = true;while (q.size()) {int u = q.front();q.pop();vis[u] = false;for (auto [v, w] : G[u]) {if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;cnt[v] = cnt[u] + 1;if (cnt[v] >= n) return make_pair(false, vector<W>());if (!vis[v]) {vis[v] = true;q.push(v);}}}}return make_pair(true, dis);
}

Dijkstra 算法

過程

將節點分成兩個集合：

已確定最短路長度的點集（記為 $S$ 集合）。
未確定最短路長度的點集（記為 $T$ 集合）。

初始時，所有節點都屬于集合 $T$ 。

令 $dis_s=0$ ，其他點的 $dis$ 為 $\infty$ 。

接下來，重復以下操作：

從 $T$ 集合中，選擇一個 $dis$ 最小的節點，移到 $S$ 集合中。
對這個節點的所有出邊進行松弛： $dis_v=min(dis_v,dis_u+w(u,v))$ 。

注意，帶負權的圖不能使用 Dijkstra 算法。

代碼

// G - 圖
// s - 源點
template<class W>
vector<W> dijkstra(const Graph<W>& G, int s) {int n = G.size();W inf = numeric_limits<W>::max();vector<W> dis(n, inf);vector<bool> vis(n, false);dis[s] = 0;for (int i = 0; i < n; i++) {int u = 0;W mind = inf;for(int j = 0; j < n; j++)if (!vis[j] && dis[j] < mind) {u = j;mind = dis[j];}vis[u] = true;for (auto [v, w] : G[u]) {dis[v] = min(dis[v], dis[u] + w);}}return dis;
}

優化

上述代碼時間復雜度是 $O(n^2)$ ，能否優化呢？

我們發現，只能優化找最小點的過程。

我們用一個小根堆來維護（按第一關鍵字）。初始時候插入 $(0,s)$ ，計算時，直接從堆頂取出的節點即是最優，然后彈出該節點。

松弛的時候，如果 $dis_v$ 發生改變，那么就插入 $(dis_v,v)$ 。

時間復雜度 $O(m \log m)$

代碼

template<class W>
vector<W> dijkstra(const Graph<W>& G, int s) {int n = G.size();W inf = numeric_limits<W>::max();priority_queue<pair<W, int>, vector<pair<W, int>>, greater<pair<W, int>>> q;vector<W> dis(n, inf);vector<bool> vis(n, false);dis[s] = 0;q.emplace(0, s);while (q.size()) {int u = q.top().second;q.pop();if (vis[u]) continue;vis[u] = true;for (auto& [v, w] : G[u]) {if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;q.emplace(dis[v], v);}}}return dis;
}

下一次，我們將學習多源最短路。?

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/bicheng/15184.shtml
繁體地址，請注明出處：http://hk.pswp.cn/bicheng/15184.shtml
英文地址，請注明出處：http://en.pswp.cn/bicheng/15184.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！