在前面的文章中，對於圖的構建以及廣搜和深搜有了介紹，今天就帶來一個新的知識點，即最短路徑問題。 最短路徑問題是圖論研究中的一個經典算法問題， 旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。
相關文章
迪傑斯特拉算法
迪傑斯特拉(Dijkstra)算法解決最短路徑問題，其創造者：艾茲格·W·迪科斯徹 （Edsger Wybe Dijkstra）。
Dijkstra算法是從一個頂點到其餘各頂點的最短路徑算法，解決的是有權圖中最短路徑問題。
Dijkstra算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。
迪傑斯特拉算法屬於貪婪算法的應用，基本思想為：
保證每個階段選取到的頂點到起始點的路徑長度都是最短的。
在這種情況下，迪傑斯特拉算法只需要不斷計算更新選取的頂點到其鄰接頂點的路徑長度就可以了，這對於路徑長度必然是遞增的（無權或非負權）圖來說，
是沒有問題的，因為，對於它們來說，每一步的最優解就是整體的最優解。
然而，對於 負權圖 來說，就不是這樣的了，負權的存在，會導致一種情況的發生：
v0->v1 權值3 v0->v2 權值2 v1->v2 權值-1
那麼以v0為起點時，Dijkstra算法得到最短路徑為
v0->v1 3 v0->v2 2
實際上，最短路徑
v0->v2->v1 2 v0->v2 2
實現過程
首先對於源點本身，其最短距離為0，然後源點可以直達(不需要其他頂點作為中介)的頂點，其最短距離是權值本身(負權圖除外)，
不可直達的頂點，其權值等於源點到中介頂點的距離+中介頂點到目標頂點的距離(如果發現更短的權值，則替代)，所以建立兩個
數組，一個保存最短路徑 s[]，一個保存是否已經走過 vis[]。
V0->V1 的權值為1 V0->V2 的權值為3 V1->V3 的權值為1 V2->V3 的權值為1
如果以V0作為起點，首先s[]初始值設為INT_MAX，然後將V0的最短路徑s[0]設置0。
第一步:遍歷所有頂點(用u表示),如果頂點u未走過，且s[u]
第一輪遍歷最小值就是起點V0，因為上面將s[0]設置為0
第二步:對第一步得到的頂點u，將其設置為走過，vis[u] = 1 ,然後獲取u可達的頂點，重製他們的最短路徑。
也就是V1和V2需要重置最短距離。目的s[1]和s[2]為INT_MAX，新的 s[1] = s[0]+1 (1是上面規定V0->V1的權值) s[2] = s[0]+3 (3是上面規定V0->V2的權值)
新舊比較，發現新的小於舊的值，那麼替換s[1]和s[2].如果大於則無視。
第三步:使用第一步的邏輯，再次遍歷。
第二輪遍歷最小值是V1 因為s[1]
第四步:使用第二步邏輯，得到u=1,其可達頂點為V3，此時V3的最短距離為INT_MAX ,新的最短距離s[3] = s[1]+1(1是上面規定V1->V3的權值)，
那麼s[3]被重置為2。
第五步:繼續按照第一步的邏輯遍歷，目前最短距離，且沒有走的頂點是V3。
第六步:按照第二步的邏輯，找到V3可達頂點，發現沒有V3可達的頂點，則無視
第七步:再次按照第一步的邏輯遍歷，目前最短距離，且沒有走的頂點是V2。
第八步:按照第二步的邏輯，找到V2可達頂點，為V3，此時舊的s[3]為2，新的s[3] = s[2]+1 = 4.
因為新的s[3]>舊的s[3]，那麼無需考慮
第九步，結束，目前s[] = {0,1,3,2}。
上面推導步驟有些多，但是實際上總是在重複第一步和第二步，就是遍歷頂點個數次，每次鬆弛頂點的權值。
注:
對於負權圖無效是因為在某個頂點局部最優的時候，可能其他邊因為負權的情況，導致最終頂點不是最優路徑
實現代碼(C++)
//
// main.cpp
// Dijkstra
//
// Created by 陳龍
// Copyright © 2019 陳龍. All rights reserved.
//
#include
#include
using namespace std;
//頂點個數
const int N = 6;
//結構體
struct Graph{
//頂點
int v;
//邊權
int w;
Graph(int _v,int _w):v(_v),w(_w){};
};
//鄰接表
vector ver[N];
//是否遍歷
int vis[N];
//最短路徑
int S[N];
//初始化
void init(){
//將路徑長度存入S，如果不可達，則無窮大
int MAX=INT_MAX;
//遍歷頂點，初始化S
for (int i=0; i S[u] + g.w ) {
S[g.v] =S[u] + g.w ;
}
}
}
}
int main(int argc, const char * argv[]) {
// insert code here...
init();
for (int i=0; i 
