最短路徑計算分為靜態最短路徑計算和動態最短路徑計算。
靜態路徑最短路徑算法是在不改變外部環境的情況下計算最短路徑。主要有Dijkstra算法和A*(A星)算法。
動態路徑最短路徑是在外部環境不斷變化的情況下計算最短路徑，即預測無法計算。例如，在壹個敵人或障礙物不斷移動的遊戲中。有壹個典型的D*算法。
這是用Drew程序實現的10000個節點的隨機路網的最短路徑。
真實路網中計算k條路徑的例子:從節點5696到節點3006，最快的三條路徑，可以看出路徑基本走環路或主幹道。黑線第壹，藍線第二，紅線第三。約束系數為1.2。* * *享受部分章節。顯示計算部分完全由德魯自己開發的程序完成。
參見K路徑算法測試程序。
Dijkstra算法求最短路徑；
Dijkstra算法是壹種典型的最短路徑算法，用於計算從壹個節點到所有其他節點的最短路徑。主要特征是從起點向外擴展，直到終點。Dijkstra算法可以得到最短路徑的最優解，但由於遍歷節點較多，效率較低。
Dijkstra算法是壹種非常具有代表性的最短路徑算法，在很多專業課程中都作為基礎內容進行了詳細的介紹，比如數據結構、圖論、運籌學等等。
Dijkstra壹般有兩種表達方式，壹種是使用永久和臨時標簽，另壹種是使用開閉表。為了和下面要介紹的A*算法和D*算法保持壹致，Drew在這裏使用了打開表和關閉表。
大致流程:
創建兩個表，打開和關閉。
打開的表保存所有已經生成但沒有調查的節點，關閉的表記錄已經訪問過的節點。
1.訪問路網中起點最近且未檢查過的點，並將該點放入開放組中進行檢查。
2.從開表中找出最接近起始點的點，找出該點的所有子節點，將該點放入閉表中。
3.遍歷該點的子節點。求這些子節點與起點的距離，將子節點放入打開的表中。
4.重復步驟2、3和3。直到打開的表為空或者找到目標點。
這是壹個Dijkstra算法在drew程序中在4000個節點的隨機道路網絡上搜索最短路徑的演示。黑色圓圈表示已經遍歷和計算的點。從圖中我們可以看到，Dijkstra算法是從起點延伸到周圍各層，經過大量節點的計算，到達目標點。所以速度慢，效率低。
有很多方法可以提高Dijkstra的搜索速度。據Drew所知，常用的方法是數據結構的二叉堆和從起點和終點同時搜索的Dijkstra。
推薦網頁:u.edu.cn/assist/js04/ZJS045/ZJS04505/zjs045050a.htm.
簡單介紹Dijkstra算法，帶圖形顯示和源代碼下載。
A*(A星)算法:啟發式算法。
A*(A-Star)算法是求解靜態路網中最短路徑的最有效方法。
公式為:f(n)=g(n)+h(n)，
其中f(n)是從初始點到目標點的節點n的評價函數，
G(n)是狀態空間中從初始節點到第n個節點的實際成本，
H(n)是從n到目標節點的最佳路徑的估計成本。
尋找最短路徑(最優解)的關鍵在於評價函數h(n)的選擇:
估計值h (n) < =從n到目標節點的距離的實際值。這種情況下，要搜索的點多，搜索範圍大，效率低。但是可以得到最優解。
如果估計值>；實際值，搜索點數少，搜索範圍小，效率高，但不能保證最優解。
估計值越接近實際值，得到的評價函數就越好。
例如，對於壹個幾何路網，可以取兩個節點之間的歐幾裏德距離(直線距離)作為估計值，即f = g(n)+sqrt((dx-NX)*(dx-NX)+(dy-NY)*(dy-NY))；這樣，當G的值不變時，評價函數F或多或少會受到評價值H的限制，當節點靠近目標點時，H的值較小，F的值也相對較小，可以保證搜索到終點的最短路徑。在無方向的四處搜索上明顯優於Dijstra算法。
啟發式條件
樂觀(必須小於或等於實際成本)
盡可能接近真實成本
主要搜索過程:
創建兩個表，打開的表保存所有已經生成但沒有調查的節點，關閉的表記錄已經訪問過的節點。
遍歷當前節點的每個節點，將n節點放入CLOSE，取n節點的子節點x，-->計算x的估計值->；
而(開！=空)
{
從開放表中取出具有最小估計值f的節點n；
If(n節點= =目標節點)break
其他
{
If(X in OPEN)比較兩個X的估計值f //註意是同壹節點兩條不同路徑的估計值。
if(x的估計值小於開表的估計值)
更新開放表中的估計值；//取最小路徑的估計值。
if(CLOSE中的X)比較兩個X的估計值//註意是同壹節點的兩條不同路徑的估計值。
if(x的估計值小於CLOSE表的估計值)
更新結算表中的估計值；將X節點放入OPEN //中，得到最小路徑的估計值。
如果(X不在兩者中)
求x的估計值；
並將x插入到打開的表中；//尚未排序
}
在關閉表中插入n個節點；
根據估計值對開放表中的節點進行排序；//其實就是比較開放表中節點F的大小，從路徑最短的節點向下進行。
}