Python数模笔记-NetworkX（2）最短路径
1、最短路徑問題的常用算法
最短路徑問題是圖論研究中的經典算法問題，用于計算圖中一個頂點到另一個頂點的最短路徑。
歡迎關注 Youcans 原創系列，每周更新數模筆記
Python數模筆記-PuLP庫
Python數模筆記-StatsModels統計回歸
Python數模筆記-Sklearn
Python數模筆記-NetworkX
Python數模筆記-模擬退火算法
1.1 最短路徑長度與最短加權路徑長度
在日常生活中，最短路徑長度與最短路徑距離好像并沒什么區別。但在具體的圖論問題中卻可能是不同的概念和問題，經常會被混淆。
圖論中有無權圖和有權圖，無權圖中的邊沒有權，賦權圖的邊帶有權，可以表示距離、時間、費用或其它指標。在問題文字描述中，往往并不直接指出是無權圖還是有權圖，這時就要注意最短路徑與最短加權路徑的區別。路徑長度是把每個頂點到相鄰頂點的長度記為 1，而不是指這兩個頂點之間道路的距離——兩個頂點之間的道路距離是連接邊的權（weight）。通俗地說，路徑長度可以認為是飛行棋的步數，或者公交站點的站數，相鄰頂點之間為一步，相隔幾個頂點就是幾站。路徑長度是從路徑起點到終點的步數，計算最短路徑是要計算從起點到終點步數最小的路徑。
如果問題不涉及頂點之間的距離，要求從起點到終點的最短路徑及對應的最短長度，是指從這條路線從起點到終點有幾站，在圖論中稱為最短路徑長度。但是，如果問題給出頂點之間的道路長度或距離，姑且稱為各路段的距離，要求從起點到終點的最短路徑及對應的最短距離，顯然并不是在找經過最少步數的路徑，而是在找路徑中各路段的距離之和最小的路徑，在圖論中稱為最短加權路徑長度——這里權重是路段距離。
1.2 最短路徑的常用算法
求解最短路徑長度的常用算法是 Dijkstra 算法、Bellman-Ford 算法和Floyd 算法，另外還有啟發式算法 A*。
- Dijkstra 算法
Dijkstra 算法用于計算有權圖中最短路徑問題 。該算法從起點開始，采用貪心法策略，每次遍歷到起點距離最近且未訪問過的頂點的鄰接節點， 直到擴展到終點為止。
Dijkstra 算法的時間復雜度為 O(n^2)。如果邊數遠小于 n^2，可以用堆結構將復雜度降為O((m+n)log(n))。
Dijkstar算法不能處理負權邊。
- Bellman-Ford 算法
Bellman-Ford 算法用于求解單源最短路徑問題。算法原理是對圖進行 V-1次松弛操作，得到所有可能的最短路徑。
Bellman-Ford 算法的時間復雜度高達 O(V*E)，V、E 分別是頂點和邊的數量。
Bellman-Ford 算法可以處理負權邊。其基本操作“拓展”是在深度上搜索，而“松弛”操作則在廣度上搜索，因此可以對負權邊進行操作而不影響結果。
- Floyd 算法
Floyd 算法又稱插點法，利用動態規劃思想求解有權圖中多源點之間最短路徑問題。算法從圖的帶權鄰接矩陣開始，遞歸地進行 n 次更新得到圖的距離矩陣，進而可以得到最短路徑節點矩陣。
Floyd 算法的時間復雜度為 O(n^3)，空間復雜度為 O(n^2)。算法時間復雜度較高，不適合計算大量數據。Floyd 算法的優點是可以一次性求解任意兩個節點之間的最短距離，對于稠密圖的效率高于執行 V 次 Dijkstra算法。
Floyd 算法可以處理負權邊。
- A* 算法
A*算法是一種靜態路網中求解最短路徑最有效的直接搜索方法。
A*算法是啟發式算法，采用最好優先（Best-first）搜索策略，基于估價函數對每個搜索位置的評估結果，猜測最好的位置優先進行搜索。
A*算法極大地減少了低質量的搜索路徑，因而搜索效率很高，比傳統的路徑規劃算法實時性更高、靈活性更強；但是，A*算法找到的是相對最優路徑，不是絕對的最短路徑，適合大規模、實時性高的問題。
1.3 最短路徑算法的選擇
2、NetworkX 中的最短路徑算法
2.1 無向圖和有向圖的最短路徑求解函數
| shortest_path(G[, source, target, weight,…]) | 計算圖中的最短路徑 |
| all_shortest_paths(G, source, target[,…]) | 計算圖中所有最短的簡單路徑 |
| shortest_path_length(G[, source, target, …]) | 計算圖中的最短路徑長度 |
| average_shortest_path_length(G[, weight, method]) | 計算平均最短路徑長度 |
2.2 無權圖最短路徑算法
| single_source_shortest_path(G, source[,cutoff]) | 計算從源到所有可達節點的最短路徑 |
| single_source_shortest_path_length(G,source) | 計算從源到所有可達節點的最短路徑長度 |
| single_target_shortest_path(G, target[,cutoff]) | 計算從所有可達節點到目標的最短路徑 |
| single_target_shortest_path_length(G,target) | 計算從所有可達節點到目標的最短路徑長度 |
| all_pairs_shortest_path(G[, cutoff]) | 計算所有節點之間的最短路徑 |
| all_pairs_shortest_path_length(G[, cutoff]) | 計算所有節點之間的最短路徑長度 |
2.3 有權圖最短路徑算法
| dijkstra_path(G, source, target[, weight]) | 計算從源到目標的最短加權路徑 |
| dijkstra_path_length(G, source, target[,weight]) | 計算從源到目標的最短加權路徑長度 |
| all_pairs_dijkstra_path(G[, cutoff, weight]) | 計算所有節點之間的最短加權路徑 |
| all_pairs_dijkstra_path_length(G[, cutoff,… ]) | 計算所有節點之間的最短加權路徑長度 |
| bellman_ford_path(G, source, target[, weight]) | 計算從源到目標的最短路徑 |
| bellman_ford_path_length(G, source, target) | 計算從源到目標的最短路徑長度 |
| all_pairs_bellman_ford_path(G[, weight]) | 計算所有節點之間的最短路徑 |
| all_pairs_bellman_ford_path_length(G[,weight]) | 計算所有節點之間的最短路徑長度 |
| floyd_warshall(G[, weight]) | 用 Floyd 法計算所有節點之間的最短路徑長度 |
| floyd_warshall_numpy(G[, nodelist, weight]) | 用 Floyd 法計算所有指定節點之間的最短路徑長度 |
3、NetworkX 中的 Dijkstra 算法
NetworkX 中關于 Dijkstra 算法提供了 13 個函數，很多函數的功能是重疊的。這里只介紹最基本的函數 dijkstra_path() 和 dijkstra_path_length()。
3.1 dijkstra_path() 和 dijkstra_path_length() 使用說明
dijkstra_path() 用于計算從源到目標的最短加權路徑，dijkstra_path_length() 用于計算從源到目標的最短加權路徑長度。
dijkstra_path(G, source, target, weight=‘weight’)
dijkstra_path_length(G, source, target, weight=‘weight’)
主要參數：
- G(NetworkX graph)：圖。
- source (node)：起點。
- target (node)：終點。
- weight (string or function)：參數為字符串(string)時，按該字符串查找邊的屬性作為權重；如果該字符串對應的邊屬性不存在，則權重置為1；參數為函數時，邊的權重是函數的返回值。
返回值：
dijkstra_path() 的返回值是最短加權路徑中的節點列表，數據類型為list。
dijkstra_path_length() 的返回值是最短加權路徑的長度（路徑中的邊的權重之和），數據類型為 number。
3.2 dijkstra_path() 算法使用例程
本案例問題來自：司守奎、孫兆亮，數學建模算法與應用（第2版），P43，例4.3，國防工業出版社。
例4.3：無向圖的最短路問題。已知如圖的有權無向圖，求頂點 v1 到 頂點 v11 的最短路徑。
# networkX_E2.py # Demo of shortest path with NetworkX # Copyright 2021 YouCans, XUPT # Crated：2021-05-18import matplotlib.pyplot as plt # 導入 Matplotlib 工具包 import networkx as nx # 導入 NetworkX 工具包# 問題 2：無向圖的最短路問題（司守奎，數學建模算法與應用，P43，例4.3） G2 = nx.Graph() # 創建：空的 無向圖 G2.add_weighted_edges_from([(1,2,2),(1,3,8),(1,4,1),(2,3,6),(2,5,1),(3,4,7),(3,5,5),(3,6,1),(3,7,2),(4,7,9),(5,6,3),(5,8,2),(5,9,9),(6,7,4),(6,9,6),(7,9,3),(7,10,1),(8,9,7),(8,11,9),(9,10,1),(9,11,2),(10,11,4)]) # 向圖中添加多條賦權邊: (node1,node2,weight) # 兩個指定頂點之間的最短加權路徑 minWPath_v1_v11 = nx.dijkstra_path(G2, source=1, target=11) # 頂點 0 到 頂點 3 的最短加權路徑 print("頂點 v1 到 頂點 v11 的最短加權路徑: ", minWPath_v1_v11) # 兩個指定頂點之間的最短加權路徑的長度 lMinWPath_v1_v11 = nx.dijkstra_path_length(G2, source=1, target=11) #最短加權路徑長度 print("頂點 v1 到 頂點 v11 的最短加權路徑長度: ", lMinWPath_v1_v11) # === 關注 Youcans 原創系列（https://blog.csdn.net/youcans）=== pos = nx.spring_layout(G2) # 用 FR算法排列節點 nx.draw(G2, pos, with_labels=True, alpha=0.5) labels = nx.get_edge_attributes(G2,'weight') nx.draw_networkx_edge_labels(G2, pos, edge_labels = labels) plt.show()3.3 程序運行結果
頂點 v1 到 頂點 v11 的最短加權路徑: [1, 2, 5, 6, 3, 7, 10, 9, 11] 頂點 v1 到 頂點 v11 的最短加權路徑長度: 133.4 程序說明
4、NetworkX 中的 Bellman-Ford 算法
NetworkX 中關于 Bellman-Ford 算法提供了 13 個函數，很多函數的功能是重疊的。這里只介紹最基本的函數 bellman_ford_path() 和 bellman_ford_path_length()。
4.1 bellman_ford_path() 和 bellman_ford_path_length() 使用說明
bellman_ford_path() 用于計算從源到目標的最短加權路徑，bellman_ford_path_length() 用于計算從源到目標的最短加權路徑長度。
bellman_ford_path(G, source, target, weight=‘weight’)
bellman_ford_path_length(G, source, target, weight=‘weight’)
主要參數：
- G(NetworkX graph)：圖。
- source (node)：起點。
- target (node)：終點。
- weight (string)：按字符串查找邊的屬性作為權重。默認值為權重 ‘weight’。
返回值：
bellman_ford_path() 的返回值是最短加權路徑中的節點列表，數據類型為list。
bellman_ford_path_length() 的返回值是最短加權路徑的長度（路徑中的邊的權重之和），數據類型為 number。
4.2 bellman_ford_path() 算法使用例程
本案例問題來自：司守奎、孫兆亮，數學建模算法與應用（第2版），P41，例4.1，國防工業出版社。
例4.1：城市間機票價格問題。已知 6個城市之間的機票票價如矩陣所示（無窮大表示沒有直航），求城市 c1 到其它城市 c2…c6 的票價最便宜的路徑及票價。
# networkX_E1.py # Demo of shortest path with NetworkX # Copyright 2021 YouCans, XUPT # Crated：2021-05-18import pandas as pd import matplotlib.pyplot as plt # 導入 Matplotlib 工具包 import networkx as nx # 導入 NetworkX 工具包# 問題 1：城市間機票價格問題（司守奎，數學建模算法與應用，P41，例4.1） # # 從Pandas數據格式（頂點鄰接矩陣）創建 NetworkX 圖 # # from_pandas_adjacency(df, create_using=None) # 鄰接矩陣，n行*n列，矩陣數據表示權重 dfAdj = pd.DataFrame([[0, 50, 0, 40, 25, 10], # 0 表示不鄰接，[50, 0, 15, 20, 0, 25],[0, 15, 0, 10, 20, 0],[40, 20, 10, 0, 10, 25],[25, 0, 20, 10, 0 ,55],[10, 25, 0, 25, 55, 0]]) G1 = nx.from_pandas_adjacency(dfAdj) # 由 pandas 頂點鄰接矩陣 創建 NetworkX 圖# 計算最短路徑：注意最短路徑與最短加權路徑的不同 # 兩個指定頂點之間的最短路徑 minPath03 = nx.shortest_path(G1, source=0, target=3) # 頂點 0 到 頂點 3 的最短路徑 lMinPath03 = nx.shortest_path_length(G1, source=0, target=3) #最短路徑長度 print("頂點 0 到 3 的最短路徑為：{}，最短路徑長度為：{}".format(minPath03, lMinPath03)) # 兩個指定頂點之間的最短加權路徑 minWPath03 = nx.bellman_ford_path(G1, source=0, target=3) # 頂點 0 到 頂點 3 的最短加權路徑 # 兩個指定頂點之間的最短加權路徑的長度 lMinWPath03 = nx.bellman_ford_path_length(G1, source=0, target=3) #最短加權路徑長度 print("頂點 0 到 3 的最短加權路徑為：{}，最短加權路徑長度為：{}".format(minWPath03, lMinWPath03))for i in range(1,6):minWPath0 = nx.dijkstra_path(G1, source=0, target=i) # 頂點 0 到其它頂點的最短加權路徑lMinPath0 = nx.dijkstra_path_length(G1, source=0, target=i) #最短加權路徑長度print("城市 0 到 城市 {} 機票票價最低的路線為: {}，票價總和為：{}".format(i, minWPath0, lMinPath0)) # === 關注 Youcans 原創系列（https://blog.csdn.net/youcans）=== # nx.draw_networkx(G1) # 默認帶邊框，頂點標簽 nx.draw(G1, with_labels=True, layout=nx.spring_layout(G1)) plt.show()4.3 程序運行結果
頂點 0 到 3 的最短路徑為：[0, 3]，最短路徑長度為：1 頂點 0 到 3 的最短加權路徑為：[0, 4, 3]，最短加權路徑長度為：35 城市 0 到 城市 1 機票票價最低的路線為: [0, 5, 1]，票價總和為：35 城市 0 到 城市 2 機票票價最低的路線為: [0, 4, 2]，票價總和為：45 城市 0 到 城市 3 機票票價最低的路線為: [0, 5, 3]，票價總和為：35 城市 0 到 城市 4 機票票價最低的路線為: [0, 4]，票價總和為：25 城市 0 到 城市 5 機票票價最低的路線為: [0, 5]，票價總和為：104.4 程序說明
通過本案例，可以直觀地理解最短路徑長度與最短加權路徑長度的區別。
版權說明：
本文內容及例程為作者原創，并非轉載書籍或網絡內容。
本文中案例問題來自：
1、司守奎、孫兆亮，數學建模算法與應用（第2版），國防工業出版社。
YouCans 原創作品
Copyright 2021 YouCans, XUPT
Crated：2021-05-18
歡迎關注 Youcans 原創系列，每周更新數模筆記
Python數模筆記-PuLP庫（1）線性規劃入門
Python數模筆記-PuLP庫（2）線性規劃進階
Python數模筆記-PuLP庫（3）線性規劃實例
Python數模筆記-NetworkX（1）圖的操作
Python數模筆記-NetworkX（2）最短路徑
Python數模筆記-NetworkX（3）條件最短路徑
Python數模筆記-StatsModels 統計回歸（1）簡介
Python數模筆記-StatsModels 統計回歸（2）線性回歸
Python數模筆記-StatsModels 統計回歸（3）模型數據的準備
Python數模筆記-StatsModels 統計回歸（4）可視化
Python數模筆記-Sklearn （1）介紹
Python數模筆記-Sklearn （2）聚類分析
Python數模筆記-Sklearn （3）主成分分析
Python數模筆記-Sklearn （4）線性回歸
Python數模筆記-Sklearn （5）支持向量機
Python數模筆記-模擬退火算法（1）多變量函數優化
Python數模筆記-模擬退火算法（2）約束條件的處理
Python數模筆記-模擬退火算法（3）整數規劃問題
Python數模筆記-模擬退火算法（4）旅行商問題
總結
以上是生活随笔為你收集整理的Python数模笔记-NetworkX（2）最短路径的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： swift面向对象之属性
- 下一篇： 【OpenCV 例程200篇】28. 图