一、bellman_ford

1. 是什么松弛

在《算法四》中，對松弛的解釋是：relax the edge，看起來比較抽象，不過如果我們從生活中的實例去理解，就簡單多了：
試想一根繩索，當你握著繩索的兩頭使勁用力拉伸時，繩子緊繃，長度會變長；而當你減小用力時，繩子松弛，長度會變短。當你沒有用任何力時，此時繩子的長度最短。
這里當用力減小時，繩子收到的拉力減小，進而長度變短的過程，就是“松弛的過程”
體現在圖論中，就是對于任意邊 a->b，所謂的松弛操作就是通過 dist[b]=min(dist[b], dist[a]+g[a][b]) 來更新最短路的過程。
通過松弛操作，繩子變短，即起點到終點的距離逐漸趨近于最短路。
所以說，圖論中常說的松弛操作就是一個“比喻”說法。它將最短路和繩子做類比。很有意思😊
在不同的算法中，松弛的具體操作（形式）可能不同，不過它們的本質都是相同的，那就是減小起點到終點的距離使其最終趨近于最短路。

2. 限定最短路的邊數

為什么 bellman_ford 算法的松弛操作可以限定最短路？

從圖中我們就可以發現，對所有邊的松弛過程有點像“層序遍歷”的過程，具體來說，以起點為出發點的層次遍歷：我們每次從上一輪拓展出的結點出發，拓展下一個相鄰的結點。形式上就相當于多走了一條邊。對于圖示，就是：
第一輪：從起點1拓展2，3
第二輪：從2，3拓展出4，5
第三輪：從4，5拓展出3，6

可以發現，3被拓展了兩次

通過這我們也能證明出 bellman_ford 算法的正確性，只要我們松弛 n-1 次，那么就一定能得到起點到終點的最短路。因為此時我們是相當于枚舉了所有從起點走到終點的情況。
即，先枚舉走 1 條邊到終點的情況；再枚舉走 2 條邊到終點的情況，…，最后枚舉走 n-1 條邊到終點的情況。并且對于走 k 條邊的情況，還會枚舉所有可能的路線，最后對其結果取最小值。
但是這也說明了，bellman_ford 求最短路的過程是 “暴力枚舉”，因此它的時間效率不高。主要用于限定邊數的最短路。

3. 不可達的點

對于不可達的點，我們的松弛會導致從起點到該點的距離減小。例如我們只有一條邊 2->3，權值為 -1，那么松弛之后將導致 dist[3]=dist[2]-1。在初始狀態下，dist[2]=dist[3]=INF。
你可能很聰明的想到，哎，按你這么說，bellman_ford 算法看起來完全不像層次遍歷了啊，因為在初始狀態下，我們只拓展了起點（1），它可以不從起點進行拓展呀（2->3）。
沒錯，但問題是，不從起點（上一輪拓展的點）開始拓展的點，是無意義的，因為我們不能保證其可達性，就如我們上面的說的，1->2 和 1->3 都不可達，那么從 2 開始拓展 3 有什么意義呢？

二、spfa

SPFA算法（Shortest Path Faster Algorithm），也稱為 bellman_ford 隊列優化算法。

SPFA的稱呼來自 1994年西南交通大學段凡丁的論文，其實Bellman_ford 提出后不久 （20世紀50年代末期） 就有隊列優化的版本，國際上不承認這個算法是是國內提出的。 所以國際上一般稱呼 該算法為 Bellman_ford 隊列優化算法（Queue improved Bellman-Ford）

1. spfa優化了什么

在上面 bellman_ford 算法中，每一輪松弛需要對所有邊進行操作，時間復雜度為 O(M)，效率很低。
但其實就如我們上面所提到的，每次松弛看起來就是層序遍歷，而對于層序遍歷來說，每一次只需要從最末端元素開始遍歷即可，之前已經遍歷過的元素就無需再遍歷了。
其實這里的松弛操作也是類似的，對于 1->2 這條邊，我們只需要在第一輪遍歷即可，在第二輪和第三輪中就無需對這條邊進行松弛了，因為 dist[a] 值已經確定了，它不會在變化。
由此可見，每一輪都枚舉所有邊是無意義的。并且，我們可以總結出：對于 a->b 這條邊，只要當 dist[a] 發生變化時，松弛這條邊才有意義。否則如果 dist[a] 不變，那么 dist[a]+g[a][b] 也不變，判斷 dist[a]+g[a][b] 和 dist[b] 的大小從而進行松弛就完全沒有意義了。
因此，我們可以用一個隊列來保存這些 dist 發生變化的起始點 a，然后只對以 a 為起點的邊進行松弛操作。這就是隊列優化的 bellman_ford 算法。

同樣我們可能理解為什么在 spfa 中，一個點可以多次入隊了，就如我們上面說的，對于 2->5 這條邊，我們需要在第二輪和第三輪時進行遍歷。由于它需要分別在兩輪進行松弛操作，那么 2 這個點就需要入隊兩次。每次入隊就相當于一輪松弛。
同樣的我們也能解釋為什么 spfa 一個點不可達，但是從起點到他的距離變小了，因為 spfa 本質上就是 bellman_ford 啊，所以他繼承了 bellman_ford 的這個問題。

2. 時間復雜度

如何設計卡掉spfa的數據
隊列優化版Bellman_ford 的時間復雜度 并不穩定，效率高低依賴于圖的結構。
例如 如果是一個雙向圖，且每一個節點和所有其他節點都相連的話，那么該算法的時間復雜度就接近于 Bellman_ford 的 O(N * E)， N 為節點數量，E為邊的數量。
在這種圖中，每一個節點都會重復加入隊列 n-1 次，因為 這種圖中每個節點都有 n-1 條指向該節點的邊，每條邊指向該節點，就需要加入一次隊列。
當然這種圖是比較極端的情況，也是最稠密的圖。所以如果圖越稠密，則 SPFA的效率越接近與 Bellman_ford。反之，圖越稀疏，SPFA的效率就越高。
一般來說，SPFA 的時間復雜度為 O(K * N)， K 為不定值，因為節點需要計入幾次隊列取決于圖的稠密度。
如果圖是一條線形圖且單向的話，每個節點的入度為1，那么只需要加入一次隊列，這樣時間復雜度就是 O(N)。
所以 SPFA 在最壞的情況下是 O(N * E)，但一般情況下時間復雜度為 O(K * N)。
盡管如此，以上分析都是 理論上的時間復雜度分析。
并沒有計算 出隊列 和 入隊列的時間消耗。 因為這個在不同語言上 時間消耗也是不一定的。
以C++為例，以下兩段代碼理論上，時間復雜度都是 O(n) ：

for (long long i = 0; i < n; i++) {k++;
}

for (long long i = 0; i < n; i++) {que.push(i);que.front();que.pop();
}

在 MacBook Pro (13-inch, M1, 2020) 機器上分別測試這兩段代碼的時間消耗情況：
n = 10^4，第一段代碼的時間消耗：1ms，第二段代碼的時間消耗： 4 ms
n = 10^5，第一段代碼的時間消耗：1ms，第二段代碼的時間消耗： 13 ms
n = 10^6，第一段代碼的時間消耗：4ms，第二段代碼的時間消耗： 59 ms
n = 10^7，第一段代碼的時間消耗: 24ms，第二段代碼的時間消耗： 463 ms
n = 10^8，第一段代碼的時間消耗: 135ms，第二段代碼的時間消耗： 4268 ms
在這里就可以看出 出隊列和入隊列 其實也是十分耗時的。
SPFA（隊列優化版Bellman_ford） 在理論上 時間復雜度更勝一籌，但實際上，也要看圖的稠密程度，如果 圖很大且非常稠密的情況下，雖然 SPFA的時間復雜度接近Bellman_ford，但實際時間消耗 可能是 SPFA耗時更多。

4. 負環問題

在用 spfa 求負環時，不需要建立虛擬源點。我們只需要以任意結點為起點執行 spfa 就一定能判斷負環是否存在。因此只要存在符號，就一定存在負權邊，就一定能進行松弛操作，就一定能入隊。

3. 限制邊數的最短路

既然 spfa 是 bellman_ford 的改進版，那么按理來說，spfa 也能實現限制邊數的最短路問題。沒錯，問題是，如何在 spfa 的執行邏輯中限制松弛次數？
還是從層序遍歷的思想來看，在層序遍歷中，每一輪遍歷需要取出當前隊列中所有保存的結點。由于 spfa 是對 bellman_ford 的優化，所以 spfa 在形式上和層序遍歷更相似了。
這里的實現思路和層序遍歷非常相似:
題目鏈接

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int N = 510, M = 10010, INF = 0x3f3f3f3f;int n, m, k;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], backup[N];
bool st[N];void add(int a, int b, int c) 
{w[idx] = c;e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}int spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;queue<int> q;q.push(1);st[1] = true;while(k -- ) {memset(st, false, sizeof st);// （1）這里要將所有st置位false，因為上一輪置位true的點和這一輪需要加入的點“不一樣”// 上一輪入隊的點，我們使用的是backup[]進行松弛的// 而這一輪加入的點，我們希望使用 dist[] 進行// 可以發現，這一輪對 dist 的更新不會體現在上一輪中，因為上一輪使用 backup 而不是 dist// 因此對于上一輪入隊，st置位true的點，這一輪依然需要入隊int cnt = q.size();// （2）和bellman_ford一樣，使用上一輪的dist進行松弛操作memcpy(backup, dist, sizeof(dist));while(cnt -- ) // （3）遍歷上一層所有加入的點，進行松弛{auto t = q.front(); q.pop();st[t] = false;for(int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if(dist[j] > backup[t] + w[i]) {dist[j] = backup[t] + w[i];if(!st[j]) {q.push(j);st[j] = true;}}}}}return dist[n];
}int main()
{memset(h, -1, sizeof h);cin >> n >> m >> k;while(m -- ) {int a, b, c;   cin >> a >> b >> c;add(a, b, c);}int t = spfa();if(t >= INF / 2) puts("impossible");else    cout << t << endl;return 0;
}

通過上面的代碼其實可以發現，形式上和 spfa 差不多，不過有幾個細節需要注意，特別是 st 數組和 backup 數組的處理，詳細內容可以看代碼中的注釋部分。

三、堆優化dijkstra

1. 時間復雜度分析

reference
在C++中一般通過優先隊列priority_queue作為數據結構來優化dijkstra
當使用優先隊列時，如果同一個點的最短路被更新多次，因為先前更新時插入的元素不能被刪除，也不能被修改，只能留在優先隊列中，故優先隊列內的元素個數是 O(m) 的
每次從隊列中取出一個元素的時間復雜度為 O(logm)。故，總的時間復雜度是 O(mlogm)

四、AStar

1. 權值轉換

對于很多情景來說，我們不好直接使用 AStar 算法，特別是在需要確保“最短路”特性的前提下，找到一個合適的估價函數比較困難！例如：題目鏈接
在上面這道題目中，騎士按照日字形移動，如果我們使用 AStar 算法，是不容易找出一個合適的估價函數使得估價值小于等于真實距離的。
就比如，騎士可以從 [0,0] 移動到 [1,2]。此時的：

• 哈密頓距離為 3
• 歐拉距離為 $\sqrt{5}$
• 切比雪夫距離為 2
  他們都大于騎士的實際移動距離 1，所以說，按照實際的移動權值 1 進行移動時，很難找出合適的估價函數。
  不過如果我們將這個權值 1 看作 5（=22+11，分別沿著 x 軸和 y 軸移動） 的話。然后以歐拉距離的平方作為估價函數。那么此時估價值就一定小于等于實際值。
  因此說，通過改變權值，我們可以將原本不適用的估價函數修改為合法。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>using namespace std;const int N = 1000;
const int DISTANCE = 5; // 2 * 2 + 1 * 1typedef pair<int, int> PII;int dist[N + 1][N + 1];
int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};typedef struct Node {PII p; // pointint g, h;    // f = g(grape_dist) + h(heuristic)bool operator<(const Node &rhs) const {return g + h > rhs.g + rhs.h;}
} Node; // astar_node_typeint eular_distance(PII x, PII y)
{return (x.first - y.first) * (x.first - y.first) + (x.second - y.second) * (x.second - y.second);
}int astar_bfs(PII start, PII goal)
{if(start == goal)   return 0;memset(dist, 0, sizeof dist);dist[start.first][start.second] = 1;priority_queue<Node> q;q.push({start, 5, eular_distance(start, goal)});while(q.size()) {auto t = q.top();   q.pop();auto [x, y] = t.p;int  g = t.g;for(int i = 0; i < 8; i ++ ) {int a = x + dx[i], b = y + dy[i];if(a <= 0 || a > N || b <= 0 || b > N)   continue;  if(!dist[a][b] || dist[a][b] > dist[x][y] + 1){if(a == goal.first && b == goal.second)    return dist[x][y];q.push({{a, b}, g + DISTANCE, eular_distance({a,b}, goal)});dist[a][b] = dist[x][y] + 1;   }}}return -1;  // cant move the goal
}int main()
{int T;  cin >> T;while(T -- ) {int sx, sy, ex, ey;cin >> sx >> sy >> ex >> ey;cout << astar_bfs({sx, sy}, {ex, ey}) << endl;}return 0;
}

2. 只能確保終點的最短路

在 AStar 算法中，我們只能確保從起點到終點的最短路，而不能確保從起點到其余節點的路線也是最短路。
具體來說，當終點第一次出隊時，我們能確保它是最短路，但對于其余節點來說，我們并不能保證這一點。
這是因為我們的估價函數保證的是：任意節點到終點的估價值小于等于實際值。
如果我們相求非終點的最短路，需要確保任意節點到該節點的估價值小于等于實際值，但我們的估價函數并未保證這一點。
當然，很顯然的，如果運氣好的話，對于某些節點來說，我們的估價函數或許也滿足其余節點到該節點的估計值小于等于實際值，但這完全是運氣，它完全不可靠！
所以說，即使我們求出了非終點的最短路，也只是運氣好而已。
因此說，由于非終點第一次出隊可能不是最短路，就意味著它可能在后續再次被更新，此時就需要再次入隊。這不同于 dijkstra 和 bfs 的單次入隊。
因為 dijkstra 和 bfs 可以保證某個節點第一次出隊時一定是最短路。但 Astar 由于估計值的原因，只能保證終點。
從上面的代碼中，我們可能看出這一處理：if(!dist[a][b] || dist[a][b] > dist[x][y] + 1)
其中 dist[a][b] > dist[x][y] + 1 對某個節點做了允許多次入隊處理。如果我們去掉這段代碼，那么 bfs 的正確性完全看運氣了。
如果此時遍歷到的其余節點恰好能滿足最短路的特性，程序正確；反之，如果其余節點（中間節點）不滿足最短路，那么從其余節點出發走向終點的路線也必然不是最短路了。