本次筆記内容：
7.1.1 概述
7.1.2 無權圖的單源最短路
7.1.3 有權圖的單源最短路
7.1.3-s 有權圖的單源最短路示例
7.1.4 多源最短路算法
最短路徑問題
最短路徑問題的抽象
問題分類
無權圖的單源最短路算法
有權圖的單源最短路算法
負值圈（negative-cost cycle）
Dijkstra算法
Dijkstra時間複雜度讨論
多源最短路算法
Floyd算法
在網絡中，求兩個不同頂點之間的所有路徑中，邊的權值之和最小的那一條路徑。
這條路徑就是兩點之間的最短路徑（Shortest Path）；
第一個頂點為源點（Source）；
最後一個頂點為終點（Destination）。
單源最短路徑問題：從某固定源點出發，求其到所有其他頂點的最短路徑：
（有向/無向）無權圖
（有向/無向）有權圖
多源最短路徑問題：求任意兩頂點間的最短路徑
按照遞增（非遞減）的順序找出各個頂點的最短路。實際上就是廣度優先搜尋算法（BFS）。
dist[W] = S到W的最短距離
dist[S] = 0
path[W] = S到W的路上經過的某頂點
假設上述圖用鄰接表存儲，上述算法的時間複雜度為
T
=
O
(
∣
V
+
E
)
T=O(|V|+|E|)
T=O(∣V∣+∣E∣)。
如上圖，如果存在負值圈（negative-cost cycle），則進入無限循環。是以，我們的最短路算法都不考慮存在負值圈的情況。
算法思路依舊是按照遞增（非遞減）的順序找出各個頂點的最短路。
這個算法不能解決有負邊的情況。
（1）直接掃描所有未收錄頂點：O(|V|)
2
T=O(|V|^2+|E|)
T=O(∣V∣2+∣E∣)
對于稠密圖效果好（E與V^2同一數量級）
（2）将dist存在最小堆中：O(log|V|)
更新dist[W]的值：O(log|V|)
l
o
g
T=O(|V|log|V|+|E|log|V|)=O(|E|log|V|)
T=O(∣V∣log∣V∣+∣E∣log∣V∣)=O(∣E∣log∣V∣)
對于稀疏圖效果好（E與V同一數量級）
Dijkstra例題我已在運籌學裡學過多次，所寫項目也有所應用，示例不再記錄了。
如圖是Dijkstra的例題，現在的狀态是剛剛收錄V_5，準備通路V_5的鄰接點。
方法1：直接将單源最短路算法調用|V|遍。
3
×
T=O(|V|^3+|E| \times |V|)
T=O(∣V∣3+∣E∣×∣V∣)
對稀疏圖效果好
方法2：Floyd算法
T=O(|V|^3)
T=O(∣V∣3)
對于稠密圖效果好
如上圖，D[i][j]逐漸将各個點收錄，求包含已收錄點的最短距離。
如上圖，Floyd算法的時間複雜圖是
T=O(∣V∣3)。