【運籌學教學▪勤實踐】-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）

如有疑問，歡迎諮詢~

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