---

一、單源最短路徑–Dijkstra算法

1、簡介

單源最短路徑問題：給定一個圖G = ( V ， E ) G=(V，E)G=(V，E)，求源結點s ∈ V s∈Vs∈V到圖中每個結點v ∈ V v∈Vv∈V的最短路徑。Dijkstra算法就適用于解決帶權重的有向圖上的單源最短路徑問題，同時算法要求圖中所有邊的權重非負。一般在求解最短路徑的時候都是已知一個起點和一個終點，所以使用Dijkstra算法求解過后也就得到了所需起點到終點的最短路徑。
針對一個帶權有向圖G，將所有結點分為兩組S和Q，S是已經確定最短路徑的結點集合，在初始時為空（初始時就可以將源節點s放入，畢竟源節點到自己的代價是0），Q 為其余未確定最短路徑的結點集合，每次從Q 中找出一個起點到該結點代價最小的結點u ，將u 從Q 中移出，并放入S 中，對u 的每一個相鄰結點v 進行松弛操作。松弛即對每一個相鄰結點v ，判斷源節點s到結點u的代價與u 到v 的代價之和是否比原來s 到v 的代價更小，若代價比原來小則要將s 到v 的代價更新為s 到u 與u 到v 的代價之和，否則維持原樣。如此一直循環直至集合Q 為空，即所有節點都已經查找過一遍并確定了最短路徑，至于一些起點到達不了的結點在算法循環后其代價仍為初始設定的值，不發生變化。Dijkstra算法每次都是選擇V-S中最小的路徑節點來進行更新，并加入S中，所以該算法使用的是貪心策略。
Dijkstra算法存在的問題是不支持圖中帶負權路徑，如果帶有負權路徑，則可能會找不到一些路徑的最短路徑。

2、解析

3、代碼

		// Dijkstrala算法// dist是用來存放最小值的表的// pPath是用來存放父親下標的void Dijkstra(const V& src, std::vector<W>& dist, std::vector<int>& pPath){size_t srci = GetIndex(src);size_t n = _vertex.size();// 初始化dist表和pPath表dist.resize(n, MAX_W);pPath.resize(n, -1);dist[srci] = 0; // 當前的第一個位置的距離為0pPath[srci] = srci; // 這個可有可無// 來一個S為存放加入到集合中的已經確定了的點std::vector<bool> S(n, false);for (size_t i = 0; i < n; i++) // 遍歷n次--n個頂點{// 選最短路徑頂點且不在S更新其他路徑size_t u = 0;size_t min = MAX_W;// 遍歷輸入值的表，選最小值for (size_t i = 0; i < n; i++){if (S[i] == false && dist[i] < min) // false是沒有進行訪問過{u = i; // 更新一下當前的最短路徑的頂點min = dist[i]; // 更新點的最小值}}S[u] = true; // 將剛好訪問的這個頂點設置為true已經被訪問過的地方// 松弛算法，更新u連接頂點v  srci->u + u->v <  srci->v  更新for (size_t v = 0; v < n; v++){if (S[v] == false && dist[u] + _matrix[u][v] < dist[v] && _matrix[u][v] != MAX_W){dist[v] = dist[u] + _matrix[u][v]; // 更新一下v的點的值pPath[v] = u; // 更新父下標的點的值}}}}

4、測試用例

	void TestGraphDijkstra(){const char* str = "syztx";Graph<char, int, INT_MAX, true> g(str, strlen(str));g.AddEdge('s', 't', 10);g.AddEdge('s', 'y', 5);g.AddEdge('y', 't', 3);g.AddEdge('y', 'x', 9);g.AddEdge('y', 'z', 2);g.AddEdge('z', 's', 7);g.AddEdge('z', 'x', 6);g.AddEdge('t', 'y', 2);g.AddEdge('t', 'x', 1);g.AddEdge('x', 'z', 4);std::vector<int> dist;std::vector<int> parentPath;g.Dijkstra('s', dist, parentPath);g.PrinrtShotPath('s', dist, parentPath);}

5、打印最小路徑代碼和測試

		void PrinrtShotPath(const V& src, const std::vector<W>& dist, const std::vector<int>& parentPath){size_t N = _vertex.size();size_t srci = GetIndex(src);for (size_t i = 0; i < N; ++i){if (i == srci)continue;std::vector<int> path;int parenti = i;while (parenti != srci){path.push_back(parenti); // 先把自己存進去parenti = parentPath[parenti]; // 往父親去跳}path.push_back(srci); // 最后存初始位置reverse(path.begin(), path.end()); // 逆置一下for (auto pos : path){std::cout << _vertex[pos] << "->";}std::cout << dist[i] << std::endl;}}

6、缺陷：不能使用負路徑

const char* str = "sytx";Graph<char, int, INT_MAX, true> g(str, strlen(str));g.AddEdge('s', 't', 10);g.AddEdge('s', 'y', 5);g.AddEdge('t', 'y', -7);g.AddEdge('y', 'x', 3);std::vector<int> dist;std::vector<int> parentPath;g.Dijkstra('s', dist, parentPath);g.PrinrtShotPath('s', dist, parentPath);

二、單源最短路徑–Bellman-Ford算法

1、簡介

Dijkstra算法只能用來解決正權圖的單源最短路徑問題，但有些題目會出現負權圖。這時這個算法就不能幫助我們解決問題了，而bellman—ford算法可以解決負權圖的單源最短路徑問題。它的優點是可以解決有負權邊的單源最短路徑問題，而且可以用來判斷是否有負權回路。它也有明顯的缺點，它的時間復雜度 O(N*E) (N是點數，E是邊數)普遍是要高于Dijkstra算法O(N2)的。像這里如果我們使用鄰接矩陣實現，那么遍歷所有邊的數量的時間復雜度就是O(N^3)，這里也可以看出來Bellman-Ford就是一種暴力求解更新。

2、解析

（1）詳情

i、負權問題：一個點只跑一趟找最短路徑（問題大大的）

ii、解決負權問題：每個點在更新完最短路徑后繼續暴力再繼續遍歷更新最短路徑

原因還是因為負權路徑的問題，當我們更新完一趟的最短路徑后發現其父親節點是個負數，剛好通過這條路，而我們前面更新的最短路徑不是從這條路走的，那么就需要繼續更新前面這個父親結點的最短路徑為負數，使得這個最短路徑更新成更小的值，那么一切就說通了，我們就需要繼續更新唄，那么就繼續更新n次，每個點繼續遍歷n次。

// 進行n輪循環，原因是因為防止因為某一輪循環后值會產生更改導致的結果不正確// 所以每次進行點的詢問松弛，使得后續的路徑更新成更短路徑for (int k = 0; k < n; k++){std::cout << "第" << k << "輪次" << std::endl;}

我們跟著最終結果來看：

（2）優化

i、優化策略1：使用bool標記位跳出循環，后面循環不用跑

因為第一個輪次是將所有的路都跑一遍（初始跑一遍），第二個輪次還是從頭到尾的跑一遍，這回輪次是找負數重新更新一下最短路徑，而假如說路徑的負數并不多的時候，兩個輪次就能全部跑完了，并不需要后面冗余的n-3個輪次，所以我們給個標志位，從第i個輪次發現根本不會更改路勁的情況下我們直接退出，不需要執行下一個輪回的操作。

ii、優化策略2：使用SPFA算法優化（隊列）（未做出）

革命尚未成功，同志仍需努力…

3、代碼

		// 貝爾曼福特算法// 時間復雜度--O(N^3) 空間復雜度--O(N)bool BellmanFord(const V& src, std::vector<W>& dist, std::vector<int>& pPath){size_t n = _vertex.size();size_t srci = GetIndex(src);// vector<W> dist,記錄srci-其他頂點最短路徑權值數組dist.resize(n, MAX_W);// vector<int> pPath 記錄srci-其他頂點最短路徑父頂點數組pPath.resize(n, -1);// 先更新srci->srci為最小值dist[srci] = W();// 進行n輪循環，原因是因為防止因為某一輪循環后值會產生更改導致的結果不正確// 所以每次進行點的詢問松弛，使得后續的路徑更新成更短路徑for (int k = 0; k < n; k++){bool update = false; // 這個判斷標志是提高效率的，只需要進行相對應的輪次更新松弛即可// 第一輪都更新，第二輪往后不一定了for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){// srci->i i->jif (dist[i] + _matrix[i][j] < dist[j] && _matrix[i][j] != MAX_W){// 更新最小值+更新pPathdist[j] = dist[i] + _matrix[i][j];pPath[j] = i;update = true;}}}if (update == false){break;}}// 到這里判斷一下是否有負權回路，因為加入說是三個形成一個帶有負值回路，那么每一輪都會將值更新// 這就是負權回路問題，遇到這個負權回路問題也解決不了，那么就返回false即可for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){// srci->i i->jif (dist[i] + _matrix[i][j] < dist[j] && _matrix[i][j] != MAX_W){return false;}}}return true;}

4、測試用例及測試結果

	void TestGraphBellmanFord(){const char* str = "syztx";Graph<char, int, INT_MAX, true> g(str, strlen(str));g.AddEdge('s', 't', 6);g.AddEdge('s', 'y', 7);g.AddEdge('y', 'z', 9);g.AddEdge('y', 'x', -3);g.AddEdge('z', 's', 2);g.AddEdge('z', 'x', 7);g.AddEdge('t', 'x', 5);g.AddEdge('t', 'y', 8);g.AddEdge('t', 'z', -4);g.AddEdge('x', 't', -2);std::vector<int> dist;std::vector<int> parentPath;if (g.BellmanFord('s', dist, parentPath)){g.PrinrtShotPath('s', dist, parentPath);}else{std::cout << "存在負權回路" << std::endl;}}

5、負權回路問題

（1）問題描述和解析

我們出現負權回路的問題，大概率是出現一個環，這個環中剛好有一個或多個邊的權值是負數，如下圖所示：
那么我們想一想是否這種情況能不能避免或者是有什么算法避免？實際上一旦遇到這個問題就完蛋了，沒有任何算法能夠規避，直接說出現回路問題，不管了！

（2）出現負權問題的代碼用例及測試結果

// 微調圖結構，帶有負權回路的測試const char* str = "syztx";Graph<char, int, INT_MAX, true> g(str, strlen(str));g.AddEdge('s', 't', 6);g.AddEdge('s', 'y', 7);g.AddEdge('y', 'x', -3);g.AddEdge('y', 'z', 9);g.AddEdge('y', 'x', -3);g.AddEdge('y', 's', 1); // 新增g.AddEdge('z', 's', 2);g.AddEdge('z', 'x', 7);g.AddEdge('t', 'x', 5);g.AddEdge('t', 'y', -8); // 更改g.AddEdge('t', 'z', -4);g.AddEdge('x', 't', -2);std::vector<int> dist;std::vector<int> parentPath;if (g.BellmanFord('s', dist, parentPath)){g.PrinrtShotPath('s', dist, parentPath);}else{std::cout << "存在負權回路" << std::endl;}

三、多源最短路徑–Floyd-Warshall算法

（1）簡介

Floyd-Warshall算法是解決任意兩點間的最短路徑的一種算法。
Floyd算法考慮的是一條最短路徑的中間節點，即簡單路徑p={v1,v2,…,vn}上除v1和vn的任意節點。
設k是p的一個中間節點，那么從i到j的最短路徑p就被分成i到k和k到j的兩段最短路徑p1，p2。p1是從i到k且中間節點屬于{1，2，…，k-1}取得的一條最短路徑。p2是從k到j且中間節點屬于{1，2，…，k-1}取得的一條最短路徑。

（2）詳細解析（用圖）

除了時間復雜度太高幾乎沒別的缺點了，它允許負權路徑的存在。

（3）代碼

		// FloydWarshall算法--多源最短路徑的表示// vvDist是二維用來存放最短路徑的表格// vvpPath是二維用來存放父路徑的void FloydWarshall(std::vector<std::vector<W>>& vvDist, std::vector<std::vector<int>>& vvpPath){size_t n = _vertex.size();vvDist.resize(n); // 有多少行vvpPath.resize(n);// 初始化權值和路徑矩陣for (size_t i = 0; i < n; ++i){vvDist[i].resize(n, MAX_W); // 每一行每一列vvpPath[i].resize(n, -1);}// 先將每條邊更新一下for (size_t i = 0; i < n; i++){for (size_t j = 0; j < n; j++){if (_matrix[i][j] != MAX_W) // 當i->j點是有路的時候{vvDist[i][j] = _matrix[i][j];vvpPath[i][j] = i; // 剛好是j的前一個路徑就是i}if (i == j) // 對角線{vvDist[i][j] = W(); // 缺省的默認值}}}// 算法核心：1、中間有k的時候:i->{n個數(包含k)}->j   dist[i][k] + dist[k][j] 與 dist[i][j]比較// 2、中間沒有k的時候，那么就是i->j，也就是和上面的情況一樣了，壓根都不需要管了for (size_t k = 0; k < n/*這里k的值是n的原因在于ij也可以都包進來的*/; k++){for (size_t i = 0; i < n; i++){for (size_t j = 0; j < n; j++){// i到k有路徑 k到j有路徑if (vvDist[i][k] + vvDist[k][j] < vvDist[i][j] && vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W){vvDist[i][j] = vvDist[i][k] + vvDist[k][j];// 找跟j相連的上一個鄰接頂點// 如果k->j 直接相連，上一個點就k，vvpPath[k][j]存就是k// 如果k->j 沒有直接相連，k->...->x->j，vvpPath[k][j]存就是xvvpPath[i][j] = vvpPath[k][j]; // 動態規劃--j的前面一個元素k咯}}}}// 打印權值和路徑矩陣觀察數據for (size_t i = 0; i < n; ++i){for (size_t j = 0; j < n; ++j){if (vvDist[i][j] == MAX_W){printf("%3c", '*');}else{printf("%3d", vvDist[i][j]);}}std::cout << std::endl;}std::cout << std::endl;// 打印父路徑for (size_t i = 0; i < n; ++i){for (size_t j = 0; j < n; ++j){printf("%3d", vvpPath[i][j]); // 這里打印的是下標}std::cout << std::endl;}std::cout << "=================================" << std::endl;}

（4）運行用例及測試結果

	void TestFloydWarShall(){const char* str = "12345";Graph<char, int, INT_MAX, true> g(str, strlen(str));g.AddEdge('1', '2', 3);g.AddEdge('1', '3', 8);g.AddEdge('1', '5', -4);g.AddEdge('2', '4', 1);g.AddEdge('2', '5', 7);g.AddEdge('3', '2', 4);g.AddEdge('4', '1', 2);g.AddEdge('4', '3', -5);g.AddEdge('5', '4', 6);std::vector<std::vector<int>> vvDist;std::vector<std::vector<int>> vvParentPath;g.FloydWarshall(vvDist, vvParentPath);// 打印任意兩點之間的最短路徑for (size_t i = 0; i < strlen(str); ++i){g.PrinrtShotPath(str[i], vvDist[i], vvParentPath[i]);std::cout << std::endl;}}