最短路徑問題

最短路徑問題是組合最佳化領域的經典問題之一，它廣泛套用於計算機科學、交通工程、通信工程、系統工程、運籌學、資訊理論、控制理論等眾多領域。Dijkstra算法是經典的最短路徑算法。

基本介紹

• 中文名：最短路徑問題
• 外文名：shortest path problem
• 實質：找出圖中兩個頂點間的最短路徑
• 套用領域：計算機科學、交通工程、通信工程等

相關算法

Dijkstra算法

Dijkstra算法是經典的最短路徑算法，其基本思想是：設定一個集合S存放已經找到最短路徑的頂點，S的初始狀態只包含源點v，對vi∈V-S，假設從源點v到vi的有向邊為最短路徑。以後每求得一條最短路徑v, …, vk，就將vk加入集合S中，並將路徑v, …, vk , vi與原來的假設相比較，取路徑長度較小者為最短路徑，重複上述過程，直到集合V中全部頂點加入到集合S中。使用該算法找到的是全局最優的最短路徑，在網路節點數量大、網路邊數較多時，存在記憶體占用大、時間複雜度高等不足，並且Dijkstra算法不能很好地解決含必經點約束的最短路徑問題。

蟻群算法

蟻群算法是由Dorigo、Maniezzo和Colorni等於1991 年首先提出來的，它來源於螞蟻尋食的行為。通過研究發現，螞蟻個體之間是通過一種叫做信息素的外激素進行信息傳遞的。螞蟻在行走過程中能感知周圍信息素的強度， 並朝著信息素濃度高的方向移動，當某隻螞蟻發現食物時，它在回巢的過程當中，會在返回的路上釋放信息素作為標記，同伴發現後會沿著此路尋找到食物。當同伴中多隻螞蟻都發現了食物但路徑長短不同時，因為螞蟻在短的路徑上往返所需要的時間相對較小，所以單位時間內走過的螞蟻越來越多，在這條路徑上的信息素濃度就會越強，因此，該路徑上的螞蟻就會越來越多，逐漸選出一條最優的道路。

蟻群算法

分類

可分成兩個子問題，即單源最短路徑問題和所有頂點對之間的最短路徑問題。前者是找出從某一頂點出發到圖中所有其他頂點的最短路徑，主要算法有迪克斯徹算法等；後者是求圖中每一對頂點之間的最短路徑，主要算法有弗洛伊德算法等。

套用

通信領域

網際網路技術和套用的不斷發展，對當今網路通信流量的要求不斷增大。流量大、速度快、費用低的傳輸方式是網路傳輸的關鍵。路徑最短、代價最低的網路路由能夠大大降低通信成本、節約網路資源，提高網路資源的利用率。

交通運輸

最短路徑問題是交通分配中最基本的問題，是指一對節點之間的路徑中總阻 抗最小的路徑，幾乎所有交通流分配方法都是以它作為一個基本子過程反覆調用。