【運籌學教學?勤實踐】-1 十分鐘快速掌握最短路演算法（附C++代碼及算例）

來自專欄 數據魔術師

最近被抽查 運籌學 基本功課，

面對老師的突然發問，

機智的小編果斷選擇了——

拿 · 出

然後老師微微一笑 ：

「來，實現下解決這個問題的代碼……」

意識到上完運籌學的自己根本是條 只會解應用題 的 咸·魚，而運籌學實際上是門演算法課後...

小編痛定思痛 ，決心開始手腦結合、理論+實踐、以解決問題為目的，開始自己在運籌學上的新一輪征程！

本著一貫的無私奉獻精神，小編整理出了這些日子學習運籌學的一系列心得筆記，幫助大家快速突破理論到實踐的次元壁！

運籌學·教學筆記 第一彈 —— 最短路問題篇 先行奉上！熟悉的攻略三連（問題、方法、實現）、熟悉的實踐演示、熟悉的代碼算例...手把手帶你走上 運籌學·大佬 的征程！

內容提要：

＊什麼是最短路問題

＊單源最短路問題

＊全局最短路問題

1.什麼是最短路問題

最短路問題（shortest-path-problem）是圖論中的經典問題之一，可用來解決管路鋪設、線路安裝、廠區布局和設備更新等實際問題。

基本內容是：假設網路中的每條邊都有一個 權重（常用長度、成本、時間等表示），最短路問題的目標是找出 給定兩點（通常是源節點和匯節點）之間總權重之和最小的路徑。

如上圖所示，以1為起點，7為終點，則在此圖中，最短路徑即為 1—4—2—7。

· 常見的最短路問題 ？

根據問題約束和目標的差異，用來解決問題的演算法也會有區別。最短路問題常見的類型有：

-單源最短路問題-

包括

（1）給定起點的最短路徑問題，即給定起點，求最短路的問題；

（2）給定終點的最短路徑問題，在無向圖中等同於給定起點問題，在有向圖中等同於路徑方向相反的給定起點問題。

-全局最短路問題-

即求解任意兩點間的最短路的問題。

· 最短路問題的應用領域？

最短路問題作為圖論中的經典問題，其演算法的選擇與實現是通道路線設計的基礎,因此一直是運籌學，計算機科學與地理信息科學等領域的研究熱點。

-城市網路-

運用最短路原理可以解決交通運輸管理系統中的問題，具有非常重要的現實意義。

根據實時交通狀況，賦予城市路網中每段線路以時間權值，利用最短路原理，計算出車輛運行時間最短的路線並匯總，通過手機及時向廣大群眾發布信息，指導廣大群眾選擇行駛路線，進一步提高現有道路通行能力，提高道路服務水平。

-艦船通道-

利用圖論的經典理論和人群流量理論研究艦船人員通道路線的優化設計及最優線路選擇。

對船舶通道進行路網抽象,建立網路圖,然後以行程時間（根據人群流動的相關理論,選取不同擁擠情況下的人員移動速度,從而確定各條路段(包括樓梯)的行程時間）作為通道網路的路權，得出路阻矩陣以選擇一對起點/終點的最短時間路線為目標,建立最短路徑問題的數學模型,利用經典的演算法確定最短路徑。

上述方法可應用於艦艇多層甲板的通道網路設計及其相關問題中。

此外，很多網路相關問題均可納入最短路徑問題的應用範疇之中，如，火災救護，物流選址，網路空間建設 等等。

2.單源最短路問題

對於Dijkstra演算法解決不了的負權邊（圖中邊的權重存在負數的情況）單源最短路問題，就需要介紹解決帶負權邊圖十分有用的另一種演算法——SPFA演算法。

相關演算法的代碼將和下一部分全局最短路問題的演算法代碼一起放出。

3.全局最短路問題

單源最短路、全局最短路問題的相關演算法代碼和算例如下：

代碼及算例示例

代碼（c++版本）

算例演示

算例示例

輸入文件格式為：

SAMPLE INPUT:

n m

7 11

x y z

2 4 2

1 4 3

7 2 2

3 4 3

5 7 5

7 3 3

6 1 1

6 3 4

2 4 3

5 6 3

7 2 1

PS. n 為圖中點數，m為邊的數量；

z 為連接 x 結點和 y 結點的邊的權值。

輸出結果為：

SAMPLE OUTPUT

0 5 5 3 4 1 6

5 0 4 2 6 6 1

5 4 0 3 7 4 3

3 2 3 0 7 4 3

4 6 7 7 0 3 5

1 6 4 4 3 0 7

6 1 3 3 5 7 0

PS. 輸出結果為最短路矩陣，矩陣第 i 行、第 j 列的值即表示第 i 個結點到第 j 個結點的最短路長度。

算例演示

如上圖紅線所示，以1為起點，7為終點，則在此圖中，最短路徑即為 1—4—2—7。

上述代碼僅供分享交流學慣用，如有需要複製下面鏈接自取 ↓ ↓ ↓

http://paste.ubuntu.com/25527580/

運籌學·教學筆記 第一彈 —— 最短路問題篇 畫上句點！如果大家對 最短路問題 及 文中所敘內容 還有疑問或想要交流心得建議，歡迎移步留言區！

—end—

編輯：謝良楨（1922193128@qq.com）

賀興（hexing15@gmail.com）

代碼：賀興（hexing15@gmail.com）

指導老師：秦時明岳（professor.qin@qq.com）

如有疑問，歡迎諮詢~

更多最新數據分析相關原創文章，請關注微信公眾號：數據魔術師