背景：在圖的學習過程中，最短路徑問題是一個肯定會遇到的問題。而這個問題的原型來源于我們實際生活中的問題，例如汽車的最優路徑導航。是以為了找到解決這些實際問題的最優方案，前輩們提出了Dijkstra算法和Floyd算法，下面就來詳細地了解一下這兩個出名的算法。
現在，假設有V0~V6七個地方，每兩個地方之間的距離入下圖所示：
Dijkstra算法：O( 
最短路徑->Dijkstra算法和Floyd算法 )
這是一種貪心算法，每次找到一條權值最小的點加入到一個集合中，該集合中的所有點已經找到源點到該點的最短距離長。主要步驟如下：
建立一個資料結構Vex，包含元素weight：記錄源點到該點的暫時的最短路徑長，visited：用于判斷該點是否已經在集合中，path：用于記錄源點到該點的最短路徑。然後用一個Vex數組dis來尋找源點到各點的最短路徑長。
從dis數組中每次取出一個沒有被通路過的，且暫時最短路徑長最小的點，将該點加入到集合中。此時，dis數組中可能有些元素需要更新。将dis數組更新。
上面的說起來有點籠統，大家可能不是很了解，接下來我們用上面的圖這個執行個體來了解Dijkstra算法。
假設源點為V0，預設V0點已經在集合中，則此時V0到V1之間距離為6，是以dis[1].weight = 6，V0到V2之間不是直接相連，故dis[2].weight = MAX，表示V0到V2不可達，以此類推，dis[3].weight = 9，dis[4].weight = MAX，dis[5].weight = MAX，dis[6].weight = MAX。
從不在集合中的點中，選出一個距離最短的點，為V1，将dis[1].visited設定為true。之後再更新一下dis數組，因為V1點加入到了集合中，是以V0可以通過V1到達V2，是以此時dis[2].weight = 11，其他點不需更新。
之後再從剩下的點中選出一個距離最短的點，為V3，将dis[3].visited設定為true。之後再更新一下dis數組，因為V3點加入到了集合中，是以V0可以通過V3到達V4，是以此時dis[4].weight = 16，V0可以通過V3到達V5，是以此時dis[5].weight = 19，其他點不需更新。
之後再重複以上的步驟，直至所有的點都加入到集合中。
Dijkstra算法的代碼實作：
struct Vex{
int weight;
bool visited;
string path;
};
/**
* Dijkstra代碼實作
* @param graph 圖的矩陣表示，例如graph[0][1]表示頂點0到頂點1的權值
* @param n 頂點個數
* @param start 起始頂點
*/
void Dijkstra(int graph[][7], int n, int start){
Vex dis[n];
//初始化dis數組
for (int i = 0; i < n; ++i) {
dis[i].weight = graph[start][i];
dis[i].visited = false;
dis[i].path = to_string(start) + "->" + to_string(i);
}
dis[start].visited = true;
//每次尋找一個新的頂點的最短路徑
for (int j = 1; j < n; ++j) {
int index = 0;
int temp = MAXCOST;
//找到距離最近的頂點
for (int i = 0; i < n; ++i) {
if (dis[i].visited == false && temp > dis[i].weight){
index = i;
temp = dis[i].weight;
}
}
dis[index].visited = true;
//更新dis數組
for (int k = 0; k < n; ++k) {
if (!dis[k].visited) {
if (dis[k].weight > dis[index].weight + graph[index][k]) {
//修改最短路徑長
dis[k].weight = dis[index].weight + graph[index][k];
//修改最短路徑
dis[k].path = dis[index].path + "->" + to_string(k);
}
}
}
}
for (int l = 0; l < n; ++l) {
cout<<"點"<<start<<"到點"<<l<<"的最短距離為："<<dis[l].weight<<" 路徑為"<<dis[l].path<<endl;
}
}
/**
* 測試用例
*/
int main(){
int graph[][7] = {
0, 6, MAXCOST, 9, MAXCOST, MAXCOST, MAXCOST,
MAXCOST, 0, 5, 2, MAXCOST, MAXCOST, MAXCOST,
MAXCOST, MAXCOST, 0, MAXCOST, MAXCOST, MAXCOST, MAXCOST,
MAXCOST, MAXCOST, MAXCOST, 0, 7, 10, MAXCOST,
MAXCOST, MAXCOST, MAXCOST, MAXCOST, 0, 1, 3,
MAXCOST, MAXCOST, MAXCOST, MAXCOST, MAXCOST, 0, 8,
MAXCOST, MAXCOST, MAXCOST, MAXCOST, MAXCOST, MAXCOST, 0
};
Dijkstra(graph, 7, 0);
}
Floyd算法：O( 最短路徑->Dijkstra算法和Floyd算法 )
這是一種動态規劃算法。Dijkstra算法是求解一個點到其餘點的最短路徑，而Floyd算法是求解圖中任意兩個點之間的最短距離。相較于Dijkstra算法而言，這個算法簡單直接暴力，代碼隻有三個簡單的for循環。下面我們來分析一下Floyd算法的思路。
該算法将圖的鄰接矩陣copy了一份儲存到了一個新的二維數組graph中，例如graph[i][j]表示頂點i到頂點j的距離。初始時的graph矩陣如下：
| 6 | ∞ | 9 | ∞ | ∞ | ∞ |
| ∞ | 5 | 2 | ∞ | ∞ | ∞ |
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| ∞ | ∞ | ∞ | 7 | 10 | ∞ |
| ∞ | ∞ | ∞ | ∞ | 1 | 3 |
| ∞ | ∞ | ∞ | ∞ | ∞ | 8 |
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
現在該矩陣中任何兩點之間的路徑不經過任何中間點，例如V0與V4點不直接相連，故graph[0][4] = ∞。而我們很容易發現，如果可以經過一個中間點，比如說V1，則任何兩點之間的最短路徑長可能發生變化，例如：graph[0][2]由∞變為了11。在可以經過一個中間點的情況下，變化後的矩陣如下所示：
| 6 | 11 | 9 | ∞ | ∞ | ∞ |
| ∞ | 5 | 2 | ∞ | ∞ | ∞ |
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| ∞ | ∞ | ∞ | 7 | 10 | ∞ |
| ∞ | ∞ | ∞ | ∞ | 1 | 3 |
| ∞ | ∞ | ∞ | ∞ | ∞ | 8 |
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
我們再來思考，如果可以經過兩個中間點的話，那麼是不是某兩個點之間的距離能夠變得更近呢？比如V0到V4，如果隻經過V3點，那麼兩點之間的距離為16，如果能經過V1，V3兩個點的話，那麼兩點之間的距離為15，是以我們發現如果能同時經過兩個中間點，那麼可能某些點之間的距離能變得更近。
是以，我們在以上的基礎上，再添加一個點作為中間點。很明顯，重複以上的步驟，不斷的添加中間點，當所有的點都成為中間點時，我們就能知道圖中每兩個點之間的最短距離。
Floyd代碼實作：
/**
* Floyd代碼實作
* @param graph 圖的矩陣表示，例如graph[0][1]表示頂點0到頂點1的權值
*/
void Floyd(int graph[][7]){
//外層循環不斷的添加中間點
for (int k = 0; k < 7; ++k) {
//記憶體兩個for循環用于更新二維數組
for (int i = 0; i < 7; ++i) {
for (int j = 0; j < 7; ++j) {
if (graph[i][j] > graph[i][k] + graph[k][j]){
graph[i][j] = graph[i][k] + graph[k][j];
}
}
}
}
for (int l = 0; l < 7; ++l) {
cout<<"點0到點"<<l<<"的最短距離為-----"<<graph[0][l]<<endl;
}
}
/**
* 測試用例
*/
int main(){
int graph[][7] = {
0, 6, MAXCOST, 9, MAXCOST, MAXCOST, MAXCOST,
MAXCOST, 0, 5, 2, MAXCOST, MAXCOST, MAXCOST,
MAXCOST, MAXCOST, 0, MAXCOST, MAXCOST, MAXCOST, MAXCOST,
MAXCOST, MAXCOST, MAXCOST, 0, 7, 10, MAXCOST,
MAXCOST, MAXCOST, MAXCOST, MAXCOST, 0, 1, 3,
MAXCOST, MAXCOST, MAXCOST, MAXCOST, MAXCOST, 0, 8,
MAXCOST, MAXCOST, MAXCOST, MAXCOST, MAXCOST, MAXCOST, 0
};
Floyd(graph);
}