最短路徑問題

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

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

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

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

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