圖的表示方法
最常用的表示圖的方法是鄰接矩陣與鄰接表。
鄰接矩陣表示法
設G是一個有n(n>0)個頂點的圖，V(G)={v1, v2, …, vn}，則鄰接矩陣AG是一個n階二維矩陣。在該矩陣中，如果vi至vj有一條邊，則(i, j)項的值為1，否則為0，即：
鄰接矩陣的實作很簡單：
int edge[n][n]={};
for(...){
...
//無向圖的鄰接矩陣表示
edge[node1][node2]=;
edge[node2][node1]=;
}
鄰接表表示法
設G是一個有n(n>0)個頂點的圖，V(G)={v1, v2, …, vn}。在鄰接表中，每個頂點v都對應着一個連結清單，該連結清單的每個節點都包含一個頂點u，且(v, u)∈E(G)。因為圖中有n個頂點，是以可以利用一個長度為n的數組A，A(i)指向第i個頂點對應的連結清單的第一個節點，連結清單由頂點vi的全部鄰接頂點組成。
實作鄰接表時，可以不用連結清單，而是用vector數組的形式。
vector<int> adj[MAX];
for(int i=;i<=n-;i++) {
cin>>a>>b;
//建構無向圖的鄰接表
adj[a].push_back(b);
adj[b].push_back(a);
}
其中，adj[i]是一個vector，它記錄了結點i連通的所有結點。
Dijkstra算法
1.定義概覽
Dijkstra（迪傑斯特拉）算法是典型的單源最短路徑算法，用于計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴充，直到擴充到終點為止。注意該算法要求圖中不存在負權邊。
問題描述：在無向圖 G=(V,E) 中，假設每條邊 E[i] 的長度為 w[i]，找到由頂點 V0 到其餘各點的最短路徑。（單源最短路徑）
2.算法描述
求下圖中的1号頂點到2、3、4、5、6号頂點的最短路徑。
這裡使用二維數組e來存儲頂點之間邊的關系，初始值如下：
我們還需要用一個一維數組dis來存儲1号頂點到其餘各個頂點的初始路程，如下。
我們将此時dis數組中的值稱為最短路的“估計值”。
既然是求1号頂點到其餘各個頂點的最短路程，那就先找一個離1号頂點最近的頂點。通過數組dis可知目前離1号頂點最近是2号頂點。當選擇了2号頂點後，dis[2]的值就已經從“估計值”變為了“确定值”，即1号頂點到2号頂點的最短路程就是目前dis[2]值。
既然選了2号頂點，接下來再來看2号頂點有哪些出邊呢。有2->3和2->4這兩條邊。先讨論通過2->3這條邊能否讓1号頂點到3号頂點的路程變短。也就是說現在來比較dis[3]和dis[2]+e[2][3]的大小。其中dis[3]表示1号頂點到3号頂點的路程。dis[2]+e[2][3]中dis[2]表示1号頂點到2号頂點的路程，e[2][3]表示2->3這條邊。是以dis[2]+e[2][3]就表示從1号頂點先到2号頂點，再通過2->3這條邊，到達3号頂點的路程。
我們發現dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]>dis[2]+e[2][3]，是以dis[3]要更新為10。這個過程有個專業術語叫做“松弛”。即1号頂點到3号頂點的路程即dis[3]，通過2->3這條邊松弛成功。
這便是Dijkstra算法的主要思想：通過“邊”來松弛1号頂點到其餘各個頂點的路程。
同理通過2->4（e[2][4]），可以将dis[4]的值從∞松弛為4（dis[4]初始為∞，dis[2]+e[2][4]=1+3=4，dis[4]>dis[2]+e[2][4]，是以dis[4]要更新為4）。
剛才我們對2号頂點所有的出邊進行了松弛。松弛完畢之後dis數組為：
接下來，繼續在剩下的3、4、5和6号頂點中，選出離1号頂點最近的頂點。通過上面更新過dis數組，目前離1号頂點最近是4号頂點。此時，dis[4]的值已經從“估計值”變為了“确定值”。下面繼續對4号頂點的所有出邊（4->3，4->5和4->6）用剛才的方法進行松弛。松弛完畢之後dis數組為：
繼續在剩下的3、5和6号頂點中，選出離1号頂點最近的頂點，這次選擇3号頂點。此時，dis[3]的值已經從“估計值”變為了“确定值”。對3号頂點的所有出邊（3->5）進行松弛。松弛完畢之後dis數組為：
繼續在剩下的5和6号頂點中，選出離1号頂點最近的頂點，這次選擇5号頂點。此時，dis[5]的值已經從“估計值”變為了“确定值”。對5号頂點的所有出邊（5->4）進行松弛。松弛完畢之後dis數組為：
最後對6号頂點所有點出邊進行松弛。因為這個例子中6号頂點沒有出邊，是以不用處理。到此，dis數組中所有的值都已經從“估計值”變為了“确定值”。
最終dis數組如下，這便是1号頂點到其餘各個頂點的最短路徑。
總結一下剛才的算法。算法的基本思想是：每次找到離源點（上面例子的源點就是1号頂點）最近的一個頂點，然後以該頂點為中心進行擴充，最終得到源點到其餘所有點的最短路徑。基本步驟如下：
- 将所有的頂點分為兩部分：已知最短路程的頂點集合P和未知最短路徑的頂點集合Q。最開始，已知最短路徑的頂點集合P中隻有源點s一個頂點。我們這裡用一個book[ i ]數組來記錄哪些點在集合P中。例如對于某個頂點i，如果book[ i ]為1則表示這個頂點在集合P中，如果book[ i ]為0則表示這個頂點在集合Q中。
- 設定源點s到自己的最短路徑為0即dis=0。若存在源點有能直接到達的頂點i，則把dis[ i ]設為e[s][ i ]。同時把所有其它（即源點不能直接到達的）頂點的最短路徑為設為∞。
- 在Q中選擇一個離源點s最近的頂點u（即dis[u]最小）加入到P中。并考察所有以點u為起點的邊，對每一條邊進行松弛操作。
- 重複第3步，如果集合Q為空，算法結束。最終dis數組中的值就是源點到所有頂點的最短路徑。
算法的實作代碼如下：
int main() {
int n,m,s,t;//分别是節點數、邊的條數、起點、終點
while(cin>>n>>m>>s>>t) {
vector<vector<int>> edge(n+,vector<int>(n+,));//鄰接矩陣
vector<int> dis(n+,);//從起點出發的最短路徑
vector<int> book(n+,);//某結點已經被通路過
for(int i=;i<=n;i++)//初始化鄰接矩陣
for(int j=;j<=n;j++)
if(i!=j) edge[i][j]=INT_MAX;
int u,v,length;
for(int i=;i<m;i++) {//讀入每條邊，完善鄰接矩陣
cin>>u>>v>>length;
if(length<edge[u][v]) {//如果目前的邊長比已有的短，則更新鄰接矩陣
edge[u][v]=length;
edge[v][u]=length;
}
}
for(int i=;i<=n;i++)//初始化dis數組
dis[i]=edge[s][i];
book[s]=;//把起點先标記一下
//算法核心！！！先确定沒通路過的節點中，離起點最近的，然後松弛
for(int i=;i<=n;i++) {
int min=INT_MAX;
int index=;
for(int j=;j<=n;j++) {
if(book[j]== && dis[j]<min) {
min=dis[j];
index=j;
}
}
book[index]=;//标記這個剛剛被确定了的節點
if(index==t) break;//如果已經到終點了，就直接結束
for(int i=;i<=n;i++) {//從剛被确定的節點出發，松弛剩下的節點
if(book[i]== && edge[index][i]<INT_MAX && dis[i] > dis[index]+edge[index][i])
dis[i] = dis[index]+edge[index][i];
}
}
cout<<dis[t]<<endl;
}
return ;
}
通過上面的代碼我們可以看出，這個算法的時間複雜度是O(N2)。其中每次找到離1号頂點最近的頂點的時間複雜度是O(N)。
3. 如何記錄最短路徑
如果我們需要将那條最短路徑記錄下來，就要用到一個新數組pre[]，在更新最短路徑時，将目前節點的前一個節點記錄下來，這樣，當最終确定最短路徑後，從後往前依次檢視pre數組，就可以得到到達目前節點的最短路徑了。
Bellman-Ford算法
1. 定義概覽
Bellman-Ford算法是從DJ算法引申出來的，它可以解決帶有負權邊的最短路徑問題。值得注意的是，DJ算法和下面的Floyd算法是基于鄰接矩陣的，而Bellman-Ford算法是基于鄰接表，從邊的角度考量的。
2. 算法描述
Bellman-Ford算法用一句話概括就是：對所有的邊進行n-1次松弛操作。如果圖中存在最短路徑（即不存在負權回路），那麼最短路徑所包含的邊最多為n-1條，也就是不可能包含回路。因為如果存在正回路，該路徑就不是最短的，而如果存在負回路，就壓根就不存在所謂的最短路徑。
這裡，和用鄰接矩陣表示圖的方式不同，采用了u、v、w三個矩陣存儲邊的資訊。例如第i條邊（有向邊）存儲在u[i]、v[i]、w[i]中，表示從頂點u[i]到v[i]這條邊（u[i]->v[i]）的權值為w[i]。
之是以把dis[i]初始化為inf，可以了解成，初始時：從1号頂點通過0條邊到達其他頂點的路徑為正無窮。
int main() {
int n,m,s,t;//分别是節點數、邊的條數、起點、終點
while(cin>>n>>m>>s>>t) {
vector<int> u(*m+,);//某條邊的起點
vector<int> v(*m+,);//某條邊的終點
vector<int> length(*m+,);//某條邊的長度
vector<int> dis(n+,);//從起點出發的最短路徑
int num=;
for(int i=;i<=m;i++) {//讀入每條邊
num++;
cin>>u[num]>>v[num]>>length[num];
swap(u[num],v[num]);
}
for(int i=num+;i<=*num;i++) { //因為是無向圖，是以每條邊再複制一次，端點交換
u[i]=v[i-num];
v[i]=u[i-num];
length[i]=length[i-num];
}
num=*num;
for(int i=;i<=n;i++)//初始化dis數組
dis[i]=INT_MAX;
dis[s]=;
for(int k=;k<n;k++)
for(int j=;j<=num;j++) {
if(dis[u[j]]<INT_MAX && dis[v[j]] > dis[u[j]]+length[j])
dis[v[j]] = dis[u[j]]+length[j];
}
cout<<dis[t]<<endl;
}
return ;
}
對所有m條邊進行（n-1）輪松弛，第1輪的效果是得到從1号頂點“隻經過一條邊”到達其餘各頂點的最短路徑長度，第2輪則是得到從1号頂點“經過最多兩條邊”到達其餘各頂點的最短路徑長度，第k輪則是得到從1号頂點“經過最多k條邊”到達其餘各頂點的最短路徑長度。
SPFA算法
求單源最短路的SPFA算法的全稱是：Shortest Path Faster Algorithm。 很多時候，給定的圖存在負權邊，這時類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的複雜度又過高，SPFA算法便派上用場了。有人稱spfa算法是最短路的萬能算法。
算法思想
設立一個隊列q用來儲存待優化的結點，優化時每次取出隊首結點u，并且用u點目前的最短路徑估計值對離開u點所指向的結點v進行松弛操作，如果v點的最短路徑估計值有所調整，且v點不在目前的隊列中，就将v點放入隊尾。這樣不斷從隊列中取出結點來進行松弛操作，直至隊列空為止。
松弛操作的原理是著名的定理：“三角形兩邊之和大于第三邊”，在資訊學中我們叫它三角不等式。所謂對結點i,j進行松弛，就是判定是否dis[j]>dis[i]+w[i,j]，如果該式成立則将dis[j]減小到dis[i]+w[i,j]，否則不動。
下面舉一個執行個體來說明SFFA算法是怎樣進行的：
和BFS的差別
SPFA在形式上和廣度優先搜尋非常類似，不同的是BFS中一個點出了隊列就不可能重新進入隊列，但是SPFA中一個點可能在出隊列之後再次被放入隊列，也就是一個點改進過其它的點之後，過了一段時間可能本身被改進(重新入隊)，于是再次用來改進其它的點，這樣反複疊代下去。
代碼實作
int main() {
int n,m,s,t;//分别是節點數、邊的條數、起點、終點
while(cin>>n>>m>>s>>t) {
vector<vector<int>> edge(n+,vector<int>(n+,));//鄰接矩陣
vector<int> dis(n+,INT_MAX);//從起點出發的最短路徑
vector<int> book(n+,);//某結點在隊列中
queue<int> q;
for(int i=;i<=n;i++)//初始化鄰接矩陣
for(int j=;j<=n;j++)
if(i!=j) edge[i][j]=INT_MAX;
int u,v,length;
for(int i=;i<m;i++) {//讀入每條邊，完善鄰接矩陣
cin>>u>>v>>length;
if(length<edge[u][v]) {//如果目前的邊長比已有的短，則更新鄰接矩陣
edge[u][v]=length;
edge[v][u]=length;
}
}
dis[s]=;
book[s]=;//把起點先放入隊列
q.push(s);
int top;
while(!q.empty()) {//如果隊列非空
top=q.front();//取出隊首元素
q.pop();
book[top]=;//釋放隊首結點，因為這節點可能下次用來松弛其它節點，重新入隊
for(int i=;i<=n;i++) {
if(edge[top][i]!=INT_MAX && dis[i]>dis[top]+edge[top][i]) {
dis[i]= dis[top]+edge[top][i]; //更新最短路徑
if(book[i]==) { //如果擴充結點i不在隊列中，入隊
book[i]=;
q.push(i);
}
}
}
}
cout<<dis[t]<<endl;
}
return ;
}
如何輸出最短路徑
在一個圖中，我們僅僅知道結點A到結點E的最短路徑長度，有時候意義不大。這個圖如果是地圖的模型的話，在算出最短路徑長度後，我們總要說明“怎麼走”才算真正解決了問題。如何在計算過程中記錄下來最短路徑是怎麼走的，并在最後将它輸出呢？
我們定義一個path[]數組，path[i]表示源點s到i的最短路程中，結點i之前的結點的編号(父結點)，我們在借助結點u對結點v松弛的同時，标記下path[v]=u，記錄的工作就完成了。
如何輸出呢？我們記錄的是每個點前面的點是什麼，輸出卻要從最前面到後面輸出，這很好辦，遞歸就可以了：
void printpath(int k){
if (path[k]!=) printpath(path[k]);
cout << k << ' ';
}
Floyd算法
1.定義概覽
Floyd算法（弗洛伊德算法）是解決任意兩點間的最短路徑的一種算法，可以正确處理有向（無向）圖的最短路徑問題，同時也被用于計算有向圖的傳遞閉包。Floyd算法的時間複雜度為O(N3)，空間複雜度為O(N2)。
2.算法描述
1)算法思想原理
Floyd算法是一個經典的動态規劃算法。用通俗的語言來描述的話，首先我們的目标是尋找從點i到點j的最短路徑。從動态規劃的角度看問題，我們需要為這個目标重新做一個诠釋。
從任意節點i到任意節點j的最短路徑不外乎2種可能，一是直接從i到j，二是從i經過若幹個節點k到j。是以，我們假設Dis(i,j)為節點u到節點v的最短路徑的距離，對于每一個節點k，我們檢查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，證明從i到k再到j的路徑比i直接到j的路徑短，我們便設定Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來，當我們周遊完所有節點k，Dis(i,j)中記錄的便是i到j的最短路徑的距離。
2).算法描述
用一個數組來存儲任意兩個點之間的距離，注意，這裡可以是有向的，也可以是無向的。
當任意兩點之間不允許經過第三個點時，這些城市之間最短路程就是初始路程。
如果現在隻允許經過1号頂點，求任意兩點之間的最短路程，應該如何求呢？隻需判斷e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是從i号頂點到j号頂點之間的路程。e[i][1]+e[1][j]表示的是從i号頂點先到1号頂點，再從1号頂點到j号頂點的路程之和。其中i是1~n循環，j也是1~n循環，代碼實作如下。
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++) {
if ( e[i][j] > e[i][1]+e[1][j] )
e[i][j] = e[i][1]+e[1][j];
}
}
在隻允許經過1号頂點的情況下，任意兩點之間的最短路程更新為：
通過上圖我們發現：在隻通過1号頂點中轉的情況下，3号頂點到2号頂點（e[3][2]）、4号頂點到2号頂點（e[4][2]）以及4号頂點到3号頂點（e[4][3]）的路程都變短了。
接下來繼續求在隻允許經過1和2号兩個頂點的情況下任意兩點之間的最短路程。如何做呢？我們需要在隻允許經過1号頂點時任意兩點的最短路程的結果下，再判斷如果經過2号頂點是否可以使得i号頂點到j号頂點之間的路程變得更短。即判斷e[i][2]+e[2][j]是否比e[i][j]要小，代碼實作為如下：
//經過1号頂點
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (e[i][j] > e[i][1]+e[1][j]) e[i][j]=e[i][1]+e[1][j];
//經過2号頂點
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (e[i][j] > e[i][2]+e[2][j]) e[i][j]=e[i][2]+e[2][j];
在隻允許經過1和2号頂點的情況下，任意兩點之間的最短路程更新為：
通過上圖得知，在相比隻允許通過1号頂點進行中轉的情況下，這裡允許通過1和2号頂點進行中轉，使得e[1][3]和e[4][3]的路程變得更短了。
同理，繼續在隻允許經過1、2和3号頂點進行中轉的情況下，求任意兩點之間的最短路程。任意兩點之間的最短路程更新為：
最後允許通過所有頂點作為中轉，任意兩點之間最終的最短路程為：
整個算法過程雖然說起來很麻煩，但是代碼實作卻非常簡單，核心代碼隻有五行：
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
這段代碼的基本思想就是：最開始隻允許經過1号頂點進行中轉，接下來隻允許經過1和2号頂點進行中轉……允許經過1~n号所有頂點進行中轉，求任意兩點之間的最短路程。用一句話概括就是：從i号頂點到j号頂點隻經過前k号點的最短路程。下面給出這個算法的完整代碼：
int main() {
int n,m;
while(cin>>n>>m) {
vector<vector<int>> edge(n+,vector<int>(n+,));
for(int i=;i<=n;i++)//初始化鄰接矩陣
for(int j=;j<=n;j++)
if(i!=j) edge[i][j]=INT_MAX;
int u,v,length;
for(int i=;i<m;i++) {
cin>>u>>v>>length;
if(length<edge[u][v]) {//如果目前的邊長比已有的短，則更新鄰接矩陣
edge[u][v]=length;
edge[v][u]=length;
}
}
//核心代碼！！！5行
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(edge[i][k]!=INT_MAX && edge[k][j]!=INT_MAX && edge[i][j] > edge[i][k]+edge[k][j])
edge[i][j] = edge[i][k]+edge[k][j];
for(int i=;i<=n;i++) {//輸出最終的鄰接矩陣
for(int j=;j<=n;j++)
cout<<edge[i][j]<<' ';
cout<<endl;
}
}
return ;
}
通過這種方法我們可以求出任意兩個點之間最短路徑。它的時間複雜度是O(N3)。令人很震撼的是它竟然隻有五行代碼，實作起來非常容易。正是因為它實作起來非常容易，如果時間複雜度要求不高，使用Floyd算法來求指定兩點之間的最短路或者指定一個點到其餘各個頂點的最短路徑也是可行的。
另外需要注意的是：Floyd-Warshall算法不能解決帶有“負權回路”（或者叫“負權環”）的圖，因為帶有“負權回路”的圖沒有最短路。例如下面這個圖就不存在1号頂點到3号頂點的最短路徑。因為1->2->3->1->2->3->…->1->2->3這樣路徑中，每繞一次1->-2>3這樣的環，最短路就會減少1，永遠找不到最短路。其實如果一個圖中帶有“負權回路”那麼這個圖則沒有最短路。
3種算法的比較
适用情況
dj和ford算法用于解決單源最短路徑，而floyd算法解決多源最短路徑。
dj适用稠密圖（鄰接矩陣），因為稠密圖問題與頂點關系密切；
ford算法适用稀疏圖（鄰接表），因為稀疏圖問題與邊關系密切。
floyd在稠密圖（鄰接矩陣）和稀疏圖（鄰接表）中都可以使用；
PS：dj算法雖然一般用鄰接矩陣實作，但也可以用鄰接表實作，隻不過比較繁瑣。而ford算法隻能用鄰接表實作。
dj算法不能解決含有負權邊的圖；
而Floyd算法和Ford算法可以解決含有負權邊的問題，但都要求沒有總和小于0的負權環路。
SPFA算法可以解決負權邊的問題，而且複雜度比Ford低。形式上，它可以看做是dj算法和BFS算法的結合。
3種算法都是既能處理無向圖問題，也能處理有向圖問題。因為無向圖隻是有向圖的特例，它們隻是在鄰接矩陣或鄰接表的初始化時有所差別。
補充：A*算法
A*算法把Dijkstra算法（靠近初始點的結點）和BFS算法（靠近目标點的結點）的資訊塊結合起來。在讨論A*的标準術語中，g(n)表示從初始結點到任意結點n的代價，h(n)表示從結點n到目标點的啟發式評估代價（heuristic estimated cost）。當從初始點向目标點移動時，A*權衡這兩者。每次進行主循環時，它檢查f(n)最小的結點n，其中f(n) = g(n) + h(n)。
具體的介紹可以見這篇部落格：
連結