Lingo實戰——最短路徑問題

今天小布丁為大家分享圖論經典問題之一——最短路問題。

分享案例的網路圖及距離如下圖所示，其中不可達的路線即使用99999代表無窮大。

1.Floyd演算法

演算法的基本思想是在上一狀態集合中插入新的點，來得到新的兩點間的最短距離。第k次插入，inter(k,i,j) = min{ inter(k-1,i,j), min}，ok，了解了演算法的核心思想，我們來看看Lingo實現：

演算法注意：

1.約束表達式1和2作用在於區別第一次插入和非第一次插入。

2.smin和min的區別，離散點和集合求最小（smax，max亦同）。

3.該演算法可求得任意兩點間的最短路徑。

2.動態規劃法

動態規劃的核心思想就是當前狀態最優是由上一個狀態遞推得到，語言描述有點暈乎，還是看公式：F(i)=min，F(i)即i到達終點的最短距離。有了這個So Easy的公式，辣么Lingo實現就簡單了：

3.Dijkstra演算法

演算法核心思路是將頂點分為兩個集合（s，u），找出s到u的所有通路，並將該通路的頂點劃分到s集合，重複上訴步驟，直到所有頂點全部划到s集合，路徑查找完畢。以單源為例，詳細實現步驟如下表所示：

不知有木有小夥伴發現，單源Dijkstra演算法的實現過程本質上就是動態規劃的實現過程。有了這個發現，我們將其轉化為Lingo實現：

單源Dijkstra演算法可求得從出發點至其餘所有點的最短路徑。

4.整數線性規劃法

這裡介紹Lingo軟體提供的一個精鍊模型，值得大家仔細研究。其建模的思路非常值得大家學習和研究，利用線性規劃模型便求得網路圖的最小樹，即整個網路圖任意兩點間的最短路徑。但這個模型也有缺點，那就是當網路圖頂點過多時，該演算法計算效率將大幅降低。

通過上面四種演算法的實現，細心的小夥伴可能已經在思索，模型在實現過程中，有時候需要在Lingo編譯過程中做一些調整，達到實現模型但又可以使用Lingo編譯的平衡點。而要做到這樣靈活自如的編譯，沒有別的路徑，唯有多練習和實踐，並且吃透模型的本質。

註：有好的學習經驗願意分享給小夥伴的請隨時聯繫我，有疑問或者建議也請不要沉默。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！