前言：前面兩篇文章介紹了生成圖的最小生成樹的算法，接下來兩篇文章會介紹圖的最短路徑的算法，迪杰斯特拉算法和弗洛伊德算法。迪杰斯特拉算法是用來計算一個點到其他所有點的最短路徑，這個點稱之為源點。
一、實現流程
回憶一下我們之前學習的 Prim 算法，構建最小生成樹。從一個頂點出發，不斷地尋找離當前生成樹最近的節點，將節點加入到生成樹。而尋找源點到其他節點的最短路徑的 Dijkstra 算法，和 Prim 算法非常的類似。
因為假設當前5號節點和0號節點之間有兩條路徑，利用 Prim 算法，我們生成一個最小生成樹，那么在最小生成樹中，0 號節點和 5 號節點之間的路徑一定是最短的，也就是 Dijkstra 算法要找的最短路徑。所以整個實現流程非常的相似。和 Prim 一樣，時間復雜度也是 O(v^2)，只和頂點有關。
具體的實現流程大家可以參考 Prim算法，我就不贅述了，咱們來仔細看一下代碼實現上有什么不一樣
二、代碼實現
1、初始化常量和數據類型
#define MAX_VEX 100
#define INFINITY INT_MAX // 使用 INT_MAX 代表無窮大// 圖的結構體定義
typedef struct {int vexnum; // 節點數int arcnum; // 邊數int arcs[MAX_VEX][MAX_VEX]; // 鄰接矩陣
} MGraph;
首先我們要求源點到其他節點的最短路徑 dist，就需要用一個數組，來保存當前源點到所有節點的路徑長度。
我們需要一個數組來存儲每個節點的 path，每次更新路徑長度的時候，都需要更新當前節點的前驅結點。
另外為了防止對一個節點重復進行判斷，我們需要一個數組 final，來記錄一個節點是否已經找到最短路徑 。
// 初始化
const int v0 = 0; // 將源點硬編碼為0
int final[MaxVex]; // 記錄節點有沒有找到最短路徑
int path[MaxVex]; // 記錄每個節點的前驅結點
int dist[MaxVex]; // 記錄源點到每個節點的最短路徑
初始化的時候，根據鄰接矩陣來初始化 dist 數組，為 0 號節點到其他節點的邊的權值； final數組全部初始化為 0 表示都沒有訪問過，0號節點 final[0] 初始化為 1，表示已經訪問過；path 數組和 0 號節點直接相連的節點的 path 記為 0 ，不直接相連的節點 path 記為 -1。
// --- 1. 初始化 ---for (int i = 0; i < G.vexnum; i++) {final[i] = 0; // 所有頂點初始都未找到最短路徑dist[i] = G.arcs[v0][i]; // v0 到各點的直連距離if (dist[i] < INFINITY && i != v0) {path[i] = v0; // 如果有直連路徑, 前驅為 v0} else {path[i] = -1; // 否則無前驅}}dist[v0] = 0; // 源點到自身的距離為 0final[v0] = 1; // 源點已找到最短路徑path[v0] = -1; // 源點無前驅接下來就是主要的處理過程。首先外層需要 G.vexnum - 1 次循環，因為每次只能找到一個最近節點。內層有兩個操作需要循環：一個是找當前最近的節點；另一個是以找到的最近節點更新剩下的 dist 數組。
還要初始化一個 k 變量，用來記錄每次找到的距離 0 號節點最近的節點
// --- 2. 主循環: 每次找到一個頂點的最短路徑 ---
int k = -1; // k 用于記錄當前找到的最近頂點的索引
for (int i = 1; i < G.vexnum; i++) { // 循環 n-1 次, 找出 n-1 個頂點的最短路int min = INFINITY;// a. 尋找當前離源點最近的未訪問頂點 kfor (int j = 0; j < G.vexnum; j++) {if (!final[j] && dist[j] < min) {min = dist[j];k = j;}}// b. 將 k 標記為已找到最短路徑final[k] = 1;// c. 以 k 為跳板, 更新其他未訪問頂點的距離for (int j = 0; j < G.vexnum; j++) {// 如果 j 未被訪問, 且經過 k 到達 j 的距離更短if (!final[j] && (long)dist[k] + G.arcs[k][j] < dist[j]) {dist[j] = dist[k] + G.arcs[k][j]; // 更新距離path[j] = k; // 更新前驅}}
}
三、整體代碼
// 迪杰斯特拉算法 源點到其他節點的最短路徑
#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // 用于 INT_MAX#define MAX_VEX 100
#define INFINITY INT_MAX // 使用 INT_MAX 代表無窮大// 圖的結構體定義
typedef struct {int vexnum; // 節點數int arcnum; // 邊數int arcs[MAX_VEX][MAX_VEX]; // 鄰接矩陣
} MGraph;// 迪杰斯特拉算法 (源點默認為0)
void Dijkstra(MGraph G) {const int v0 = 0; // 將源點硬編碼為0int final[MAX_VEX]; // final[i]=1 表示已找到從 v0 到 vi 的最短路徑int path[MAX_VEX]; // path[i] 記錄 vi 的前驅頂點int dist[MAX_VEX]; // dist[i] 記錄從 v0 到 vi 的當前最短路徑長度// --- 1. 初始化 ---for (int i = 0; i < G.vexnum; i++) {final[i] = 0; // 所有頂點初始都未找到最短路徑dist[i] = G.arcs[v0][i]; // v0 到各點的直連距離if (dist[i] < INFINITY && i != v0) {path[i] = v0; // 如果有直連路徑, 前驅為 v0} else {path[i] = -1; // 否則無前驅}}dist[v0] = 0; // 源點到自身的距離為 0final[v0] = 1; // 源點已找到最短路徑path[v0] = -1; // 源點無前驅// --- 2. 主循環: 每次找到一個頂點的最短路徑 ---int k = -1; // k 用于記錄當前找到的最近頂點的索引for (int i = 1; i < G.vexnum; i++) { // 循環 n-1 次, 找出 n-1 個頂點的最短路int min = INFINITY;// a. 尋找當前離源點最近的未訪問頂點 kfor (int j = 0; j < G.vexnum; j++) {if (!final[j] && dist[j] < min) {min = dist[j];k = j;}}// b. 將 k 標記為已找到最短路徑final[k] = 1;// c. 以 k 為跳板, 更新其他未訪問頂點的距離for (int j = 0; j < G.vexnum; j++) {// 如果 j 未被訪問, 且經過 k 到達 j 的距離更短if (!final[j] && (long)dist[k] + G.arcs[k][j] < dist[j]) {dist[j] = dist[k] + G.arcs[k][j]; // 更新距離path[j] = k; // 更新前驅}}}// --- 3. 打印結果 ---printf("從源點 %d 到各頂點的最短路徑和距離如下:\n", v0);for (int i = 0; i < G.vexnum; i++) {if (i == v0) continue;printf("頂點 %d: 距離 = %-5d, 路徑: ", i, dist[i]);int temp_path[MAX_VEX];int count = 0;int p = i;while (p != -1) {temp_path[count++] = p;p = path[p];}for (int j = count - 1; j >= 0; j--) {printf("%d", temp_path[j]);if (j > 0) printf(" -> ");}printf("\n");}
}int main() {MGraph G;// 初始化圖G.vexnum = 6; // 6個頂點 (0, 1, 2, 3, 4, 5)G.arcnum = 11; // 11條邊for (int i = 0; i < G.vexnum; i++) {for (int j = 0; j < G.vexnum; j++) {if (i == j) {G.arcs[i][j] = 0;} else {G.arcs[i][j] = INFINITY;}}}// 構建一個全連通的有向圖的鄰接矩陣G.arcs[0][1] = 50;G.arcs[0][2] = 10;G.arcs[0][4] = 45;G.arcs[0][5] = 100;G.arcs[1][2] = 15;G.arcs[1][4] = 10;G.arcs[2][0] = 20;G.arcs[2][3] = 15;G.arcs[3][1] = 20;G.arcs[3][4] = 35;G.arcs[4][3] = 30;G.arcs[5][3] = 3;Dijkstra(G); // 調用函數, 無需傳入源點return 0;
}
其實和 Prim 算法只有一點不一樣，就是更新其他未訪問頂點的距離中的條件
Prim 算法是 if(lowcost[j]!=0 && G.arcs[k][j]<lowcost[j])
Dijkstra 算法是 if (!final[j] && (long)dist[k] + G.arcs[k][j] < dist[j])
前半句都是判斷節點是否已經被訪問過，只有后半句不一樣
Prim 算法是生成最小生成樹，當加入一個節點的時候，這個節點和樹中的其他節點形成一個整體，因此只要 k 這個節點到 j 的距離更小，說明 j 離生成樹的距離還可以更近，就更新 j 節點的路徑
Dijkstra 算法是計算源點到其他節點的距離，所以必須對比從 源點到k+k到j 和 dist[j]
)
