最短路徑

最短路徑（Shortest Paths）

最短路徑問題一直是圖論研究的熱點問題。例如在實際生活中的路徑規劃、地圖導航等領域有重要的應用。關于求解圖的最短路徑方法也層出不窮，本篇文章將詳細講解圖的最短路徑算法。最短路徑問題的背景問題一般是類似：已知各城市之間距離，請給出從城市A到城市B的最短行車方案 or 各城市距離一致，給出需要最少中轉方案。簡而言之：固定起始點的情況下，求最短路。

引子

下面這個例子，有向帶權圖，我們用鄰接矩陣存儲圖信息，求解任意兩點間的最短路徑。

Floyd-Warshall算法

我們來想這么一個邏輯：對于i、j兩個節點，如果想讓路徑變短，只能通過第三個節點k來中轉。從 1->5 距離為10，但 1->2->5 距離變成9了。事實上，**每個頂點都有可能使另外兩個頂點間的路程變短，**這種通過中轉變短的操作叫做松弛。

Code

Floyd-Warshall算法的原理是動態規劃，我們來看它的代碼：

def FloydWarshall(graph):n = len(graph)distance = [[graph[i][j] for j in range(n)] for i in range(n)]precursor = [[i if graph[i][j] not in [float("inf"), 0] else float("inf") for j in range(n)] for i in range(n)]for k in range(n):for i in range(n):for j in range(n):if i != j and i != k and j != k and distance[i][j] > distance[i][k] + distance[k][j]:distance[i][j] = distance[i][k] + distance[k][j]precursor[i][j] = precursor[k][j] # i -> j 更新為 i -> k -> j，j 的前驅節點更新為原來 [k][j] 位置return distance, precursor

三層循環，第一層循環中間點k，第二、第三層循環起點、終點i、j，算法的思想很容易理解：如果i到k的距離加上k到j的距離小于原先i到j的距離，那么就用這個更短的路徑長度來更新原先i到j的距離。我們可以來使用一下：

graphData = [[0, 2, float("inf"), float("inf"), 10],[float("inf"), 0, 3, float("inf"), 7],[4, float("inf"), 0, 4, float("inf")],[float("inf"), float("inf"), float("inf"), 0, 5],[float("inf"), float("inf"), 3, float("inf"), 0]]shortest, path = FloydWarshall(graphData)for item in shortest:print(item)print()for item in path:print(item)

在SciPy中有一個官方提供的floyd_warshall函數，我們可以通過調用它來驗證一下我們寫的floydWarshall算法是否正確。有些不同的地方是，在SciPy的floyd_warshall函數中如果點i和j之間不存在路徑，則前導[i，j]=-9999。

復雜度分析

Floyd-Warshall算法的時間復雜度為O(N3)，空間復雜度為O(N2)。

Dijkstra算法

有的時候我們可能只想找到從原點到某個頂點的最短路徑，比如我們打車的時候查地圖，就只需要知道從我當前位置到目的地的最短路徑就可以了。Dijkstra算法是用來計算從一個點到其它所有點的最短路徑問題，是一種單源最短路徑算法，也就是說，只能計算起點只有一個的情況。
對于圖G=<V, E>上帶權的單源最短路徑問題，Dijkstra算法設置一個集合S用來記錄已經求得最短路徑的頂點，初始時把起點v放入S中，集合S每并入一個新頂點v，都要修改原點v到集合V-S中頂點的當前最短路徑長度值。

Code

Dijkstra算法是基于貪心策略的，我們來看它的代碼：

def Dijkstra(graph, node):n, queue, visit = len(graph), list(), set()heapq.heappush(queue, (0, node))distance, precursor = [float("inf") for _ in range(n)], {node: None}distance[node] = 0while queue:dist, vertex = heapq.heappop(queue)visit.add(vertex)for i in range(n):val = graph[vertex][i]if val != float("inf") and val not in visit and dist + val < distance[i]:precursor[i] = vertexdistance[i] = dist + valheapq.heappush(queue, (dist + val, i))return distance, precursor

我們來分析一下這個算法，從起點到一個頂點的最短路徑一定會經過至少一個“中轉點”（我們認為起點也是一個“中轉點”），如果我們想要求出起點到一個頂點的最短路徑，那我們必須要先求出從起點到中轉點的最短路徑。
對于圖G=<V, E>，將所有的點分為兩類，一類是已經確定最短路徑的點，稱為“白點”，另一類是未確定最短路徑的點，稱為“藍點”。如果我們要求出一個點的最短路徑，就是把這個點由藍點變為白點，從起點到藍點的最短路徑上的中轉點在這個時刻只能是白點。
Dijkstra算法的思想：首先將起點的距離標記為0，而后進行n此循環，每次找出一個到起點距離最短的點，將它從藍點變為白點，隨后枚舉所有的藍點，如果以此白點為中轉到達某個藍點的路徑更短的話，那么就更新。我們可以來使用一下：

graphData = [[0, 2, float("inf"), float("inf"), 10],[float("inf"), 0, 3, float("inf"), 7],[4, float("inf"), 0, 4, float("inf")],[float("inf"), float("inf"), float("inf"), 0, 5],[float("inf"), float("inf"), 3, float("inf"), 0]]shortest, path = Dijkstra(graphData, 0)print(shortest, path)

在SciPy中有一個官方提供的dijkstra函數，我們可以通過調用它來驗證一下我們寫的Dijkstra算法是否正確。


注意：Dijkstra算法不能處理存在負邊權的情況。

復雜度分析

時間復雜度為O(V)。

Bellman-Ford+SPFA算法

Bellman-Ford算法與Dijkstra算法類似，都以松弛操作為基礎，即估計的最短路徑值漸漸地被更加準確的值替代，直至得到最優解。在兩個算法中，計算時每個邊之間的估計距離值都比真實值大，并且被新找到路徑的最小長度替代。
　Bellman - Ford算法基于動態規劃，反復用已有的邊來更新最短距離，Bellman-Ford算法的核心就是松弛。簡單地對所有邊進行松弛操作，共|V|-1次，其中|V|是圖中頂點的數量。對于點 v 和 u，如果 dist[u] 和 dist[v] 滿足 dist[v] > dist[u] + map[u][v]，那么dist[v] 就應該被更新為 dist[u] + map[u][v]。反復地利用上式對每條邊進行松弛，從而更新 dist[] 數組，如果沒有負權回路的話，應當會在 n - 1 次松弛之后結束算法。
SPFA是Bellman-Ford算法的一種隊列實現，減少了不必要的冗余計算，它的主要思想是：初始時將起點加入隊列，每次從隊列中取出一個元素，并對所有與它相鄰的點進行修改，若某個相鄰的點修改成功，則將其入隊，直到隊列為空時算法結束。

Code

def spfa(graph, node):n, queue = len(graph), deque()queue.append((0, node))distance, precursor = [float("inf") for _ in range(n)], [float("inf") for _ in range(n)]distance[node] = 0while queue:pair = queue.popleft()dist, vertex = pairfor i in range(n):val = graph[vertex][i]if val != float("inf") and dist + val < distance[i]:precursor[i] = vertexdistance[i] = dist + valqueue.append((dist + val, i))return distance, precursor

我們同樣也通過scipy提供的bellman_ford函數來驗證一下：

graphData = [[0, 2, float("inf"), float("inf"), 10],[float("inf"), 0, -3, float("inf"), 7],[4, float("inf"), 0, 4, float("inf")],[float("inf"), float("inf"), float("inf"), 0, 5],[float("inf"), float("inf"), 3, float("inf"), 0]]shortest, path = spfa(graphData, 0)print(shortest, path)print('-' * 75)graphData = csr_matrix(graphData)distMatrix = bellman_ford(csgraph=graphData, directed=True, indices=0, return_predecessors=True)print(distMatrix)

注意：Bellman-Ford算法不能處理存在負權回路的情況。

復雜度分析

時間復雜度為O(kE)，k是常數，平均值為2，E是邊數。

練習題

中等

LeetCode 1631. 最小體力消耗路徑
POJ 1062.昂貴的聘禮

困難

LeetCode 778. 水位上升的泳池中游泳

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的最短路径（Shortest Paths）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。