最短路徑問題是圖論研究中的一個經典算法問題， 旨在尋找圖(由結點和路徑組成的)中兩結點之間的最短路徑。 最短路徑問題是組合優化領域的經典問題之一，它廣泛應用于計算機科學、交通工程、通信工程、系統工程、運籌學、資訊論、控制理論等衆多領域。Dijkstra算法是經典的最短路徑算法。
算法具體的形式包括：(推薦學習：PHP視訊教程)
确定起點的最短路徑問題 - 即已知起始結點，求最短路徑的問題。
确定終點的最短路徑問題 - 與确定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與确定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉的确定起點的問題。
确定起點終點的最短路徑問題 - 即已知起點和終點，求兩結點之間的最短路徑。
全局最短路徑問題 - 求圖中所有的最短路徑。
Dijkstra算法
Dijkstra算法是經典的最短路徑算法，其基本思想是：設定一個集合S存放已經找到最短路徑的頂點，S的初始狀态隻包含源點v，對vi∈V-S，假設從源點v到vi的有向邊為最短路徑。以後每求得一條最短路徑v, …, vk，就将vk加入集合S中，并将路徑v, …, vk , vi與原來的假設相比較，取路徑長度較小者為最短路徑，重複上述過程，直到集合V中全部頂點加入到集合S中。使用該算法找到的是全局最優的最短路徑，在網絡節點數量大、網絡邊數較多時，存在記憶體占用大、時間複雜度高等不足，并且Dijkstra算法不能很好地解決含必經點限制的最短路徑問題。
蟻群算法
蟻群算法是由Dorigo、Maniezzo和Colorni等于1991 年首先提出來的，它來源于螞蟻尋食的行為。通過研究發現，螞蟻個體之間是通過一種叫做資訊素的外激素進行資訊傳遞的。螞蟻在行走過程中能感覺周圍資訊素的強度， 并朝着資訊素濃度高的方向移動，當某隻螞蟻發現食物時，它在回巢的過程當中，會在傳回的路上釋放資訊素作為标記，同伴發現後會沿着此路尋找到食物。當同伴中多隻螞蟻都發現了食物但路徑長短不同時，因為螞蟻在短的路徑上往返所需要的時間相對較小，是以機關時間内走過的螞蟻越來越多，在這條路徑上的資訊素濃度就會越強，是以，該路徑上的螞蟻就會越來越多，逐漸選出一條最優的道路。
分類
可分成兩個子問題，即單源最短路徑問題和所有頂點對之間的最短路徑問題。前者是找出從某一頂點出發到圖中所有其他頂點的最短路徑，主要算法有迪克斯徹算法等；後者是求圖中每一對頂點之間的最短路徑，主要算法有弗洛伊德算法等。
更多PHP相關技術文章，請通路PHP圖文教程欄目進行學習！