最短路徑shortestpath)：主要有以下兩類最短路徑問題

單源最短路徑問題：一個頂點到其他頂點的最短路徑

• 迪傑斯特拉算法(dijkstra)（帶權圖、無權圖）-本節講解
• BFS算法(無權圖)–點擊跳轉

各頂點間最短路徑問題：也就是每一對頂點間最短路徑

• 弗洛伊德算法-點擊跳轉

最短路徑在通信、交通等領域有重要應用

BFS算法隻适用于無權圖單源最短路徑，對于有權圖來說則不适用，比如下面“G港”到“R城”相對于用BFS算法找出的10來說還有一條更短的7

迪傑斯特拉算法：該算法和普利姆算法有些地方比較相似。該算法在剩餘頂點中選出一個頂點，通往這個頂點的路徑在通往所有頂點的路徑中長度是最短的

迪傑斯特拉(dijkstra)算法不便于用語言完整描述，可以跟随下面的例子體會一下這個過程。其中會涉及三個數組

• dist[]：數組存儲了當前起點到其餘頂點最短路徑的長度path[]：數組存儲了起點到其餘頂點的最短路徑（通過查詢該數組，可獲得路徑信息）final[]：數組中标記為1表示被選入最短路徑

開始時，各數組初始化如下，其中v_{0}v0有到v_{1}v1的直接路徑10、v_{0}v0​有到v_{4}v4​的直接路徑5

• 因此path[1]=0，表示v_{0}v0​有到v_{1}v1​直接路徑，其路徑長度為dist[1]=10
• 因此path[4]=0，表示v_{0}v0​有到v_{4}v4​直接路徑，其路徑長度為dist[4]=5
• final[0]=true表示此時v_{0}v0​已經被選入最短路徑了
• 由于目前v_{0}v0​到v_{2}v2​沒有路徑，因此dist[2]=\infin∞

接着，循環遍曆所有頂點，找到還沒有确定的最短路徑、且dist最小的頂點v_{i}vi​，然後final[ii]=true

• 因此選擇v_{4}v4​

在沒有加入v_{4}v4​時，那麼v_{0}v0​由于沒有路徑所以無法到達其中某些頂點，但是當v_{4}v4​加入之後情況有所改變，比如之前v_{0}v0​到v_{3}v3​是沒有路徑的，但是v_{4}v4​加入後，就有一個路徑:v_{0}v0​->v_{4}v4​->v_{3}v3​

所以我們需要對比，若final值為false，更新對應的dist和path信息

• 對于v_{1}v1​：之前v_{0}v0​->v_{1}v1​為10，但是現在:v_{0}v0​->v_{4}v4​->v_{1}v1​路徑之和為8，這是一條更短的路徑，因此将dist[1]改為8，将path[1]改為4
• 對于v_{2}v2​：之前v_{0}v0​->v_{2}v2​為\infin∞，但是現在:v_{0}v0​->v_{4}v4​->v_{2}v2​路徑之和為14，這是一條更短的路徑，因此将dist[2]改為14，将path[2]改為4
• 對于v_{3}v3​：之前v_{0}v0​->v_{3}v3​為\infin∞，但是現在:v_{0}v0​->v_{4}v4​->v_{3}v3​路徑之和為7，這是一條更短的路徑，因此将dist[3]改為7，将path[3]改為4

上面結束了第一輪，總的來說兩個步驟：

• 先在dist數組中找到一個最小的值，通往這個頂點的路徑在通往其它頂點的路徑中長度是最短的。換句話說如果你不能保證它是最小的，那就别提後面的了
• 接着由于該頂點的假如，使得前後情況有所變化，之前A到C沒有路徑，但是B加入之後，存在了一個路徑A->B->C，所以我們要判斷剛并入路徑中的頂點是否會産生一些潛在的路徑

第2輪

第3輪

第4輪，算法結束

王道視頻課并沒有介紹迪傑斯特拉(dijkstra)算法的代碼實現，但是我認為了解其代碼是十分有必要的。上述描述過程看完之後大家可能有這樣的感覺就是：“也就那樣嘛”，但這隻是紙上談兵

總的來說迪傑斯特拉算法和普利姆算法其實還是挺相似的。普利姆算法第一個小for循環是在找權值最小的邊并納入其中，迪傑斯特拉算法第一個小for循環也是在剩餘頂點中選出一個頂點，通往這個頂點的路徑在通往所有頂點的路徑中長度是最短的。普利姆算法第二個小for循環是在更新lowcost數組，是指如果剩餘的結點距離樹的距離小于之前狀況就更新，而迪傑斯特拉算法第二個for循環用于判斷剛并入路徑中的頂點的加入導緻是否會出現通往其餘頂點更短的路徑（他在判斷時，是以新加入的那個結點為起點從未被并入的結點中逐個比較

//帶權圖 typedef struct { int no; char info; }VertexType; typedef struct { float edges[maxSize][maxSize]; int n, e; VertexType vex[maxSize]; }MGraph; void Dijkstra(MGraph g, int v, int dist[], int path[]) /* dist[]數組存儲了當前起點到其餘頂點最短路徑的長度 path[]數組存儲了起點到其餘頂點的最短路徑（通過查詢該數組，可獲得路徑信息） final[]數組中标記為1表示被選入最短路徑 */ { int final[maxSize];//初始化final數組 int min, i, h, u; for (i = 0; i < g.n; i) { dist[i] = g.edges[v][i];//初始化dist數組，根據edges數組的信息，錄入根結點到其餘結點距離信息 final[i] = 0;//開始時所有結點均為被并入，故設為0 if (g.edges[v][i] < INF) /* 舉例 如果path[0][3]不是無窮大(置于無窮大會大于這個很大的數) 那麼path[3]=0，表示3這個節點之前是0，0-3是一個最短路徑 */ path[i] = v; else path[i] = -1;//如果path[3]=-1，表示之前沒有元素 } final[v] = 1;//根節點被并入 path[v] = -1;//根節點前沒有結點 ///////////////迪傑斯特拉算法核心////////////// for (i = 0; i < g.n-1; i) { min = INF; for (int j = 0; j < g.n; j) /* 此for循環每次從剩餘結點中選出一個一個結點，通過往這個 頂點的路徑在通往所有剩餘頂點的路徑中是最短的 */ { if (final[j] == 0 && dist[j] < min) { u = j; min = dist[j]; } } final[u] = 1; for (int j = 0; j < g.n; j) /* 此for循環以剛并入的結點作為中間點，對所有通往剩餘頂點的路徑進行監測 */ { if (final[j] == 0 && dist[u] g.edges[u][j] < dist[j]) { /* 如果頂點u的加入會出現通往頂點j的更短的路徑，那麼就更新信息 */ dist[j] = dist[u] g.edges[u][j]; path[j] = u; } } } }

為了使大家能夠更好地掌握這個算法，我截取了天勤視頻課中關于這一部分的代碼視頻演示，希望大家可以跟随視頻演示走一遍這個代碼的流程（代碼和天勤視頻課一緻）

Dijkstra算法代碼流程圖演示

考研數據結構中不太可能讓你寫迪傑斯特拉(dijkstra)算法的代碼，如果真要考察，最有可能的形式就是給出一個圖，讓你描述迪傑斯特拉(dijkstra)算法求解最小生成樹的過程

而這個算法又不太好用語言描述（可以說是越寫越亂），所以我推薦的方法是采用表格法，思路不亂而且特别容易描述

如下

表格如下

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!