最短路徑問題

最短路徑問題

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

基本介紹

  • 中文名:最短路徑問題
  • 外文名:shortest path problem
  • 實質:找出圖中兩個頂點間的最短路徑
  • 套用領域:計算機科學、交通工程、通信工程等
相關算法,Dijkstra算法,蟻群算法,分類,套用,通信領域,交通運輸,

相關算法

Dijkstra算法

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

蟻群算法

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

分類

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

套用

通信領域

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

交通運輸

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

相關詞條

熱門詞條

聯絡我們