【數據結構】圖論最短路徑算法深度解析：從BFS基礎到全算法綜述?

最短路徑

導讀
一、最短路徑
- 1.1 單源最短路徑
- 1.2 各頂點間的最短路徑
- 1.3 最短路徑算法
二、BFS算法
結語
- 內容回顧
- 下一篇預告：挑戰帶權最短路徑！

最短路徑

導讀

大家好，很高興又和大家見面啦！！！

歡迎繼續探索圖算法的精彩世界！在上一篇博客中，我們研究了最小生成樹（MST）問題——它專注于為整個連通圖尋找一棵連接所有頂點且總權重最小的“骨架樹”，就像鋪設覆蓋整個城市且成本最低的電網。

今天，我們將目光轉向一個同樣關鍵但目標不同的單點決策問題：最短路徑。想象你站在地圖上的一個特定起點（比如“家”），目標是以最小的累計代價（時間、距離、費用）到達圖中另一個點或所有其他點。這就是最短路徑問題的核心！

最短路徑 vs. 最小生成樹：

MST追求的是全局最優連接（覆蓋所有點）。
最短路徑追求的是點到點的最優路徑（關注起點到特定終點的序列）。

本篇核心內容：我們將

清晰理解最短路徑的基本概念和問題分類（單源SSSP、所有頂點對APSP）。
簡要羅列解決這些問題的經典算法（如Dijkstra用于非負權、Floyd用于所有頂點對）。
重點探討第一種實戰場景：如何利用 BFS（廣度優先搜索）算法，高效求解非帶權圖（邊權視為1）中的單源最短路徑問題——即從起點出發，到達圖中任一點的最少邊數/跳數路徑。
深入理解 BFS用于 最短路徑的核心思路 和 C語言實現細節。

你是否好奇原本用于圖遍歷的BFS，如何巧變身為求解最短路徑的神器？它能否處理帶權重的復雜道路？這些問題的答案，將在正文中一一揭曉。讓我們立刻開始這段從起點尋找最優路線的旅程！

一、最短路徑

要理解什么是最短路徑，這里我們以一個比較形象的例子來進行理解：

在這個地圖中，如果我們從家里出發要去學校的話，我們有多條路徑可供選擇，這里我們例舉部分路徑：

家->學校：該路徑代價為5min
家->食堂->學校：該路徑代價為6min
家->網吧->學校：該路徑代價為20min
家->網吧->食堂->學校：該路徑代價為16min
……

從這些路徑中我們不難發現我們直接選擇：家->學校這條路徑所花費的代價是最小的，因此這條路徑就是最短路徑。

下面我們就來了解以下最短路徑的定義：

最短路徑：?? 指在起點和終點之間??所有可能路徑中??，其??邊上權重總和最小的??那條路徑。??路徑是否最短取決于你如何定義邊的權重??（是距離、時間還是成本？）。

其問題本質是：在圖（由點和連接點的線組成）中，以某種代價（距離、時間、費用等）為衡量標準，尋找從起點到終點的最優路線，使得累計代價最小。??

1.1 單源最短路徑

單源最短路徑??（Single-Source Shortest Path, SSSP）是圖論中的核心問題，旨在解決：??給定一個帶權圖和指定的起點（源點），計算從該起點到圖中所有其他頂點的最短路徑及其距離??。

它不局限于單個終點，而是生成一張覆蓋全圖的“最短路徑地圖”，為后續任意終點查詢提供基礎。

1.2 各頂點間的最短路徑

所有頂點間的最短路徑（All-Pairs Shortest Paths, APSP）?? 是圖論中的一個核心問題，其目標是計算給定帶權圖中??每一對頂點之間??的最短路徑及其距離。

簡單來說，就是求解圖中??任意起點??到??任意終點??的最短路徑問題。

1.3 最短路徑算法

在最短路徑問題中，主要有以下算法用于解決最短路徑問題：

BFS（廣度優先搜索）
- 適用場景：無權圖（邊權=1），求最少邊數路徑（最小跳數）。
- 時間復雜度： $O (∣ V ∣ + ∣ E ∣)$
- 核心思想：按層次遍歷圖，首次到達終點的路徑即最短路徑。
Dijkstra 算法
- 適用場景：非負權重圖（有向/無向）。
- 時間復雜度：
  - 樸素實現： $O(|V|^2 + |E|)$
  - 堆優化（主流）： $O ((∣ V ∣ + ∣ E ∣) l o g ∣ V ∣)$
- 核心思想：貪心策略 + 優先隊列。每次從未確定點中選取距離起點最近的頂點，松弛其鄰居。
- 關鍵點：
  - 需用優先隊列（最小堆）加速。
  - 不能處理負權邊（可能導致錯誤結果）。
Bellman-Ford 算法
- 適用場景：含負權邊圖（無負環），可檢測負權環。
- 時間復雜度： $O (∣ V ∣∣ E ∣)$
- 核心思想：進行 $∣ V ∣ ? 1$ 輪松弛操作（每輪遍歷所有邊），第 $∣ V ∣$ 輪檢測負環。
A 算法*
- 適用場景：非負權重圖 + 有明確終點 + 啟發函數（加速搜索）。
- 時間復雜度：取決于啟發函數質量（最壞仍 $O ((∣ V ∣ + ∣ E ∣) l o g ∣ V ∣)$ ）。
- 核心思想：擴展 Dijkstra，引入啟發函數 $h (v)$ （估算 $v$ 到終點的代價），優先擴展 $f (v) = g (v) + h (v)$ 最小的點（ $g (v)$ 為起點到 $v$ 的實際代價）。
- 要求： $h (v)$ 必須為可采納啟發函數（不能高估真實代價）。
- 應用：游戲尋路、機器人導航（如 $h (v)$ 用歐式距離）。
Floyd-Warshall 算法
- 適用場景：所有頂點對最短路徑（APSP），支持負權邊（無負環）。
- 時間復雜度： $O(|V|^3)$
- 核心思想：動態規劃。定義 $d i s t [i] [j]$ 為通過頂點 $1.. k$ 中轉時 $i \to j$ 的最短距離，迭代更新 $k$ 。
- 核心公式： $d i s t [i] [j] = min (d i s t [i] [j], d i s t [i] [k] + d i s t [k] [j])$
Johnson 算法（高效處理帶負權的 APSP）
- 適用場景：含負權邊的稀疏圖（無負環）的 APSP 問題。
- 時間復雜度： $O (∣ V ∣∣ E ∣ l o g ∣ V ∣)$ （優于 Floyd 在稀疏圖的表現）
- 步驟：
  - 添加虛擬節點 $s$ ，連接所有頂點（邊權=0）。
  - 用 Bellman-Ford 計算 $s$ 到各點的最短距離 $h (v)$ （勢能函數）。
  - 重加權邊： $\overset{w}{^} (u, v) = w (u, v) + h (u) ? h (v)$ （新權重非負）。
  - 對每個頂點運行 Dijkstra（基于 $\overset{w}{^}$ ）。
  - 還原真實距離： $d i s t (u, v) = d i s \hat{t} (u, v) ? h (u) + h (v)$

各算法對應的應用場景如下所示：

場景需求	推薦算法
無權圖（最少邊數）	BFS
非負權圖（單源最短路徑）	Dijkstra
含負權邊（單源，需檢測負環）	Bellman-Ford
非負權圖 + 終點明確 + 需加速	A*
小規模圖或稠密圖（所有點對最短路徑）	Floyd-Warshall
含負權的稀疏圖（所有點對）	Johnson

在現階段，我們主要需要了解3種算法：

單源路徑算法（SSSP）：
- BFS算法
- Dijkstra算法
各頂點間的最短路徑（APSP）：
- Floyd算法

二、BFS算法

BFS算法用于解決非帶權圖的單源最短路徑問題。所謂的非帶權圖，我們可以視作各邊權值為1的特殊帶權圖。

在之前我們有介紹過廣度優先生成樹，整個生成樹的創建過程實際上就是由近到遠的圖遍歷過程：

生成樹的根結點就是單源最短路徑中的起點（源點）
從根結點到各結點的路徑就是單源最短路徑中起點到各結點的最短路徑

因此整個算法的實現我們可以參考廣度優先生成樹的算法實現：

通過visited[]數組來記錄當前頂點是否被訪問
通過d[]數組來記錄當前頂點到源點的最短路徑
通過path[]數組來記錄當前頂點的前驅頂點
通過隊列queue[]來實現整個遍歷過程
算法的核心邏輯為 BFS
對未訪問頂點的處理：
- 通過d[]來記錄當前頂點到原點的路徑長度
- 通過path[]來記錄當前頂點的前驅頂點
- 通過visited[]來更改當前頂點的訪問狀態

對于BFS算法的核心邏輯，我們在廣度優先遍歷的篇章中已經詳細介紹，這里就不再展開，感興趣的朋友可以點擊鏈接閱讀相關內容。

下面我們直接來看C語言代碼：

int visited[MAXVERSIZE];				// 遍歷標記數組
int d[MAXVERSIZE];						// 路徑長度數組
int path[MAXVERSIZE];					// 路徑前驅數組
void BFS_MIN_Distance(graph* g, int u) {for (int i = 0; i < MAXVERSIZE; i++) {visited[i] = false;				// 初始化所有頂點為未訪問狀態d[i] = -1;						// 初始化頂點與源點不存在路徑path[i] = -1;					// 初始化所有頂點沒有前驅頂點}visited[u] = true;					// 訪問源點d[u] = 0;							// 源點距離源點路徑長度為0path[u] = -1;						// 源點不存在前驅頂點Queue* Q = CreatQueue();			// 遍歷隊列EnQueue(Q, u);						// 源點入隊while (!IsEmpty(Q)) {int p = DeQueue(Q);				// 隊首元素出隊for (int w = FirstNeighbor(g, p); w >= 0; w = NextNeighbor(g, p, w)) {if (!visited[w]) {visited[w] = true;		// 訪問當前頂點path[w] = p;			// 當前頂點的前驅頂點為pd[w] = d[p] + 1;		// 當前頂點距離源點的距離為頂點p距離源點的距離+1EnQueue(Q, w);			// 當前頂點入隊}}}DestroyQueue(&Q);					// 銷毀隊列
}

BFS 求解單源最短路徑問題的思路很簡單，只需要在廣度優先生成樹的基礎上額外維護兩個數組用于記錄頂點距離源點的最短路徑和其前驅頂點即可。

由于解決的是非帶權圖的單源最短路徑問題，因此我們只需要對圖完成最基本的BFS即可，整個算法的時間復雜度為： $O (∣ V ∣ + ∣ E ∣)$

上述算法是在連通圖中求解單源最短路徑問題，如果是在非連通圖中，我們可以通過遍歷visited[]來找到未被訪問的頂點。這個問題在廣度優先遍歷的章節中同樣有過介紹，這里我就不再贅述。

結語

內容回顧

通過本篇博客，我們一起深入探討了最短路徑問題的核心概念與應用場景。主要內容總結如下：

最短路徑問題本質
- 在帶權圖中尋找起點到終點之間累計權重最小的路徑（如最短時間、最短距離或最小成本路徑），是解決實際路線規劃問題的理論基礎。
問題分類與算法全景
- 單源最短路徑（SSSP）：從指定起點到所有其他頂點的最短路徑（如導航起點到全城地點）。
- 所有頂點間的最短路徑（APSP）：計算圖中任意兩點間的最短路徑（如城市交通網全局分析）。
簡要介紹了六類主流算法（BFS、Dijkstra、Bellman-Ford、A*、Floyd、Johnson）及其適用場景 。
BFS算法的實戰應用
- 重點解析了如何利用廣度優先搜索（BFS）高效解決無權圖的最短路徑問題：
  - 將無權圖視為邊權均為1的特殊帶權圖，通過 d[]數組記錄距離、path[]數組回溯路徑
  - 基于層次遍歷特性，首次訪問的路徑即為最短路徑，時間復雜度僅 $O (V + E)$
  - 提供完整C語言實現代碼，適用于網絡路由、社交關系等最小跳數應用場景