前面介紹了圖的應用——01最小生成樹章節，大家可以通過下面的鏈接學習：
圖——圖的應用01最小生成樹（Prim算法與Kruskal算法詳解）
今天就講一下圖的其他應用——最短路徑，拓撲排序及關鍵路徑。
目錄
一，最短路徑
1，Dijkstra（迪杰斯特拉）算法
Dijkstra算法思想
c語言中Dijkstra算法的完整代碼：?
2，?Floyd（弗洛伊德）算法
?Floyd算法思想：
c語言中Floyd算法的完整代碼：
二，拓撲排序
三，關鍵路徑
一，最短路徑
兩種常見的最短路徑問題：
一、 單源最短路徑—用Dijkstra（迪杰斯特拉）算法
二、所有頂點間的最短路徑—用Floyd（弗洛伊德）算法
1，Dijkstra（迪杰斯特拉）算法
Dijkstra算法思想
1.初始化：先找出從源點v0到各終點vk的直達路徑（v0,vk），即通過一條弧到達的路徑。
2.選擇：從這些路徑中找出一條長度最短的路徑（v0,u）。
3.更新：然后對其余各條路徑進行適當調整，即：
從v0到其余各點的最短路徑--按路徑長度遞增次序求解?
1、把V分成兩組：
(1) S：已求出最短路徑的頂點的集合。
(2) T=V -S：尚未確定最短路徑的頂點集合。
2、將T中頂點按最短路徑遞增的次序加入到S中，
保證：
(1)從源點v0到S中各頂點的最短路徑長度都不大于從v0到T中任何頂點的最短路徑長度。
(2)每個頂點對應一個距離值：
S中頂點：從v0到此頂點的最短路徑長度。
T中頂點：從v到此頂點的只包括S中頂點作中間頂點的最短路徑長度。
下面是一個實例——
c語言中Dijkstra算法的完整代碼：?
#include <stdio.h>
#include <limits.h>#define V 9// 函數minDistance用于找到距離源節點最近的節點
int minDistance(int dist[], int sptSet[]) {int min = INT_MAX, min_index;// 遍歷所有節點，找到距離源節點最近的節點for (int v = 0; v < V; v++)if (sptSet[v] == 0 && dist[v] <= min)min = dist[v], min_index = v;return min_index;
}// 函數printSolution用于打印最短路徑
void printSolution(int dist[]) {printf("Vertex \t\t Distance from Source");// 遍歷所有節點，打印最短路徑for (int i = 0; i < V; i++)printf("%d \t\t %d", i, dist[i]);
}// 函數dijkstra用于計算最短路徑
void dijkstra(int graph[V][V], int src) {int dist[V];int sptSet[V];// 初始化距離數組和最短路徑集合for (int i = 0; i < V; i++)dist[i] = INT_MAX, sptSet[i] = 0;dist[src] = 0;// 遍歷所有節點，計算最短路徑for (int count = 0; count < V - 1; count++) {int u = minDistance(dist, sptSet);sptSet[u] = 1;// 更新距離數組for (int v = 0; v < V; v++)if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])dist[v] = dist[u] + graph[u][v];}printSolution(dist);
}int main() {int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},{4, 0, 8, 0, 0, 0, 0, 11, 0},{0, 8, 0, 7, 0, 4, 0, 0, 2},{0, 0, 7, 0, 9, 14, 0, 0, 0},{0, 0, 0, 9, 0, 10, 0, 0, 0},{0, 0, 4, 14, 10, 0, 2, 0, 0},{0, 0, 0, 0, 0, 2, 0, 1, 6},{8, 11, 0, 0, 0, 0, 1, 0, 7},{0, 0, 2, 0, 0, 0, 6, 7, 0}};dijkstra(graph, 0);return 0;
}?結果如下：
?Vertex ?? ? Distance from Source
0 ?? ? 0
1 ?? ? 4
2 ?? ? 12
3 ?? ? 19
4 ?? ? 21
5 ?? ? 11
6 ?? ? 9
7 ?? ? 8
8 ?? ? 14
2，?Floyd（弗洛伊德）算法
求所有頂點間的最短路徑有兩種方法：
方法一：每次以一個頂點為源點，重復執行Dijkstra算法n次。
方法二：弗洛伊德(Floyd)算法。
?Floyd算法思想：
1、逐個頂點試探；
2、從𝑣𝑖v_i到𝑣𝑗v_j的所有可能存在的路徑中
3、選出一條長度最短的路徑
c語言中Floyd算法的完整代碼：
與之前同樣使用了“limits”庫，?"INF"表示兩個頂點之間沒有路徑。使用INT_MAX來表示無窮大，當兩個頂點之間沒有直接路徑時，它們的距離就是無窮大。
#include <stdio.h>
#include <limits.h>#define V 4// 打印最短路徑矩陣
void printSolution(int dist[][V]);// Floyd-Warshall算法
void floydWarshall(int graph[][V]) {int dist[V][V], i, j, k;// 初始化距離矩陣for (i = 0; i < V; i++)for (j = 0; j < V; j++)dist[i][j] = graph[i][j];// 三重循環，計算最短路徑for (k = 0; k < V; k++) {for (i = 0; i < V; i++) {for (j = 0; j < V; j++) {if (dist[i][k] + dist[k][j] < dist[i][j])dist[i][j] = dist[i][k] + dist[k][j];}}}// 打印最短路徑矩陣printSolution(dist);
}// 打印最短路徑矩陣
void printSolution(int dist[][V]) {printf("以下是最短路徑矩陣：");for (int i = 0; i < V; i++) {for (int j = 0; j < V; j++) {if (dist[i][j] == INT_MAX)printf("%7s", "INF");elseprintf("%7d", dist[i][j]);}printf(" \n");}
}int main() {int graph[V][V] = {{0, 5, INT_MAX, 10},{INT_MAX, 0, 3, INT_MAX},{INT_MAX, INT_MAX, 0, 1},{INT_MAX, INT_MAX, INT_MAX, 0}};// 調用Floyd-Warshall算法floydWarshall(graph);return 0;
}
輸出結果：?
?以下是最短路徑矩陣：
? ?0 ? ? 5 ? ? 8 ? ? 9
?INF ? ? 0 ? ? 3 ? ? 4
?INF ?INF ? ? 0 ? ? 1
?INF ?INF ?INF ? ? 0
二，拓撲排序
首先我們需要知道拓撲排序是針對有向無環圖（DAG）的，在實例中，我們經常用有向圖來描述一個工程或系統的進行過程。一個工程可以分為若干個子工程，只要完成了這些子工程（活動），就可以導致整個工程的完成。
表示活動有兩種方式：
① AOV網(Activity? On Vertices)—用頂點表示活動的網絡，對應拓撲排序算法
② AOE網(Activity? On Edges)—用邊表示活動的網絡，對應關鍵路徑算法
比如教學計劃的制定
哪些課程是必須先修的，哪些課程是可以并行學習的
AOV網特點
1.若從頂點Vi到頂點Vj有路徑（有向邊），則Vi 是Vj 的（直接）前驅； Vj 是Vi 的（直接）后繼。
2.AOV網不能存在回路。
3.拓撲排序，所有頂點排成一個線性序列。
無環有向圖的判斷方法：?若網中頂點都在拓撲有序序列中，則AOV-網。不存在環。
拓撲排序算法的思想：重復選擇沒有直接前驅的頂點。
具體步驟如下：?
1.輸入AOV網絡。令 n 為頂點個數。
2.在AOV網絡中選一個沒有直接前驅的頂點, 并輸出之;
3.從圖中刪去該頂點, 同時刪去所有它發出的有向邊;
重復以上 2、3 步, 直到：
?????????全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；
?????????或：
????????圖中還有未輸出的頂點，但已跳出處理循環。這說明圖中還剩下一些頂點，它們都有直接前驅，再也找不到沒有前驅的頂點了。這時AOV網絡中必定存在有向環。
我們仍以教學計劃的制定為例分析此過程：
?對學生選課工程圖進行拓撲排序，得到的拓撲有序序列為
? ? ? C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7
或??C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6?
三，關鍵路徑
????????用途：估算工程項目完成時間
????????AOE網絡：定義結點為事件，有向邊的指向表示事件的執行次序。單位是時間（時刻）。有向邊定義為活動，它的權值定義為活動進行所需要的時間。
??? 術語：
??? 源點：表示整個工程的開始點，也稱起點（入度為0）。
??? 收點：表示整個工程的結束點，也稱匯點（出度為0）。
求解關鍵路徑，我們還需要知道以下概念：?
?那么該如何求這些值？
???? Ve(j) 及 Vl(j)）的求法：
?我們可以看出，關鍵路徑就是通過加總最長路徑上所有活動的持續時間來確定的項目最短完成時間。
下面是另一個例子
因此我們就求出了此活動的關鍵路徑
圖的應用章節就到此結束啦，不知道大家有沒有掌握呢?
如果文章對你有用的話請點個贊支持一下吧！
)
