最佳路徑演算法
⑴ 關於時間依賴的最短路徑演算法
Dijkstra 最短路徑演算法的一種高效率實現*
隨著計算機的普及以及地理信息科學的發展，GIS因其強大的功能得到日益廣泛和深入的應用。網路分析作為GIS最主要的功能之一，在電子導航、交通旅遊、城市規劃以及電力、通訊等各種管網、管線的布局設計中發揮了重要的作用，而網路分析中最基本最關鍵的問題是最短路徑問題。最短路徑不僅僅指一般地理意義上的距離最短，還可以引申到其他的度量，如時間、費用、線路容量等。相應地，最短路徑問題就成為最快路徑問題、最低費用問題等。由於最短路徑問題在實際中常用於汽車導航系統以及各種應急系統等（如110報警、119火警以及醫療救護系統），這些系統一般要求計算出到出事地點的最佳路線的時間應該在1 s～3 s內，在行車過程中還需要實時計算出車輛前方的行駛路線，這就決定了最短路徑問題的實現應該是高效率的。其實,無論是距離最短、時間最快還是費用最低，它們的核心演算法都是最短路徑演算法。經典的最短路徑演算法——Dijkstra演算法是目前多數系統解決最短路徑問題採用的理論基礎，只是不同系統對Dijkstra演算法採用了不同的實現方法。
據統計，目前提出的此類最短路徑的演算法大約有17種。F.Benjamin Zhan等人對其中的15種進行了測試，結果顯示有3種效果比較好，它們分別是：TQQ（graph growth with two queues）、DKA (the Dijkstra's algorithm implemented with approximate buckets) 以及 DKD (the Dijkstra�s algorithm implemented with double buckets )，這些演算法的具體內容可以參見文獻〔1〕。其中TQQ演算法的基礎是圖增長理論，較適合於計算單源點到其他所有點間的最短距離；後兩種演算法則是基於Dijkstra的演算法，更適合於計算兩點間的最短路徑問題〔1〕。總體來說，這些演算法採用的數據結構及其實現方法由於受到當時計算機硬體發展水平的限制，將空間存儲問題放到了一個很重要的位置，以犧牲適當的時間效率來換取空間節省。目前，空間存儲問題已不是要考慮的主要問題，因此有必要對已有的演算法重新進行考慮並進行改進，可以用空間換時間來提高最短路徑演算法的效率。
1 經典Dijkstra演算法的主要思想
Dijkstra演算法的基本思路是：假設每個點都有一對標號 (dj, pj)，其中dj是從起源點s到點j的最短路徑的長度 (從頂點到其本身的最短路徑是零路(沒有弧的路)，其長度等於零)；pj則是從s到j的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑演算法的基本過程如下：
1) 初始化。起源點設置為：① ds=0, ps為空;② 所有其他點: di=∞, pi= ;③ 標記起源點s，記k=s,其他所有點設為未標記的。
2) 檢驗從所有已標記的點k到其直接連接的未標記的點j的距離，並設置：
dj=min〔dj, dk+lkj〕
式中，lkj是從點k到j的直接連接距離。
3) 選取下一個點。從所有未標記的結點中，選取dj 中最小的一個i：
di=min〔dj, 所有未標記的點j〕
點i就被選為最短路徑中的一點，並設為已標記的。
4) 找到點i的前一點。從已標記的點中找到直接連接到點i的點j*，作為前一點,設置：
i=j*
5) 標記點i。如果所有點已標記，則演算法完全推出，否則，記k=i，轉到2) 再繼續。
2 已有的Dijkstra演算法的實現
從上面可以看出，在按標記法實現Dijkstra演算法的過程中，核心步驟就是從未標記的點中選擇一個權值最小的弧段，即上面所述演算法的2)～5)步。這是一個循環比較的過程，如果不採用任何技巧，未標記點將以無序的形式存放在一個鏈表或數組中。那麼要選擇一個權值最小的弧段就必須把所有的點都掃描一遍，在大數據量的情況下，這無疑是一個制約計算速度的瓶頸。要解決這個問題，最有效的做法就是將這些要掃描的點按其所在邊的權值進行順序排列，這樣每循環一次即可取到符合條件的點，可大大提高演算法的執行效率。另外，GIS中的數據 (如道路、管網、線路等)要進行最短路徑的計算，就必須首先將其按結點和邊的關系抽象為圖的結構，這在GIS中稱為構建網路的拓撲關系 (由於這里的計算與面無關，所以拓撲關系中只記錄了線與結點的關系而無線與面的關系，是不完備的拓撲關系)。如果用一個矩陣來表示這個網路，不但所需空間巨大，而且效率會很低。下面主要就如何用一個簡潔高效的結構表示網的拓撲關系以及快速搜索技術的實現進行討論。
網路在數學和計算機領域中被抽象為圖，所以其基礎是圖的存儲表示。一般而言，無向圖可以用鄰接矩陣和鄰接多重表來表示，而有向圖則可以用鄰接表和十字鏈表〔4〕 表示，其優缺點的比較見表 1。
表 1 幾種圖的存儲結構的比較
Tab. 1 The Comparsion of Several Graph for Storing Structures
名 稱 實現方法 優 點 缺 點 時間復雜度
鄰接矩陣 二維數組 1. 易判斷兩點間的關系 佔用空間大 O(n2+m*n)
2. 容易求得頂點的度
鄰接表 鏈表 1. 節省空間 1. 不易判斷兩點間的關系 O(n+m)或O(n*m)
2. 易得到頂點的出度 2. 不易得到頂點的入度
十字鏈表 鏈表 1. 空間要求較小 結構較復雜 同鄰接表
2.易求得頂點的出度和入度
鄰接多重表 鏈表 1. 節省空間 結構較復雜 同鄰接表
2. 易判斷兩點間的關系
目前,對於演算法中快速搜索技術的實現，主要有桶結構法、隊列法以及堆棧實現法。TQQ、DKA 以及 DKD 在這方面是比較典型的代表。TQQ雖然是基於圖增長理論的，但是快速搜索技術同樣是其演算法實現的關鍵，它用兩個FIFO的隊列實現了一個雙端隊列結構來支持搜索過程〔1〕。
DKA和DKD是採用如圖 1 所示的桶結構來支持這個運算，其演算法的命名也來源於此。在DKA演算法中，第i個桶內裝有權值落在 〔b*i, (i+1)*b) 范圍內的可供掃描的點，其中b是視網路中邊的權值分布情況而定的一個常數。每一個桶用隊列來維護，這樣每個點有可能被多次掃描，但最多次數不會超過b次。最壞情況下，DKA的時間復雜度將會是O(m*b+n(b+C/b))，其中，C為圖中邊的最大權值。DKD將點按權值的范圍大小分裝在兩個級別的桶內，高級別的桶保存權值較大的點，相應的權值較小的點都放在低級別的桶內，每次掃描都只針對低級別桶中的點。當然隨著點的插入和刪除，兩個桶內的點是需要動態調整的。在DKA演算法中，給每個桶一定的范圍以及DKD中使用雙桶，在一定程度上都是以空間換時間的做法，需要改進。
圖 1 一個桶結構的示例
Fig. 1 An Example of the Bucket Data Structure
3 本文提出的Dijkstra演算法實現
3.1 網路拓撲關系的建立
上面介紹的各種圖的存儲結構考慮了圖在理論上的各種特徵，如有向、無向、帶權、出度、入度等。而GIS中的網路一般為各種道路、管網、管線等，這些網路在具有圖理論中的基本特徵的同時，更具有自己在實際中的一些特點。首先，在GIS中大多數網路都是有向帶權圖，如道路有單雙向問題，電流、水流都有方向（如果是無向圖也可歸為有向圖的特例），且不同的方向可能有不同的權值。更重要的一點是，根據最短路徑演算法的特性可以知道，頂點的出度是個重要指標，但是其入度在演算法里則不必考慮。綜合以上4種存儲結構的優缺點， 筆者採用了兩個數組來存儲網路圖，一個用來存儲和弧段相關的數據（Net-Arc List），另一個則存儲和頂點相關的數據（Net-Node Index）。Net-Arc List用一個數組維護並且以以弧段起點的點號來順序排列，同一起點的弧段可以任意排序。這個數組類似於鄰接矩陣的壓縮存儲方式，其內容則具有鄰接多重表的特點，即一條邊以兩頂點表示。Net-Node Index則相當於一個記錄了頂點出度的索引表，通過它可以很容易地得到此頂點的出度以及與它相連的第一條弧段在弧段數組中的位置。此外，屬性數據作為GIS不可少的一部分也是必須記錄的。這樣，計算最佳路徑所需的網路信息已經完備了。在頂點已編號的情況下，建立Net-Arc List和Net-Node Index兩個表以及對Net-Arc List的排序，其時間復雜度共為O(2n+lgn)，否則為O(m+2n+lgn)。這個結構所需的空間也是必要條件下最小的，記錄了m個頂點以及n條邊的相關信息，與鄰接多重表是相同的。圖 2 是採用這個結構的示意圖。
3.2 快速搜索技術的實現
無論何種演算法，一個基本思想都是將點按權值的大小順序排列，以節省操作時間。前面已經提到過，這兩個演算法都是以時間換空間的演算法，所以在這里有必要討論存儲空間問題 (這部分空間的大小依賴於點的個數及其出度)。根據圖中頂點和邊的個數可以求出頂點的平均出度e=m/n（m為邊數，n為頂點數），這個數值代表了圖的連通程度，一般在GIS的網路圖中，e∈〔2,5〕。這樣,如果當前永久標記的點為t個，那麼，下一步需掃描點的個數就約為t～4t個。如果採用鏈表結構，按實際應用中的網路規模大小，所需的總存儲空間一般不會超過100 K。所以完全沒有必要採用以時間換空間的做法，相反以空間換時間的做法是完全可行的。在實現這部分時，筆者採用了一個FIFO隊列，相應的操作主要是插入、排序和刪除，插入和刪除的時間復雜度都是O(1)，所以關鍵問題在於選擇一個合適的排序演算法。一般可供選擇的排序演算法有快速排序、堆排序以及歸並排序等，其實現的平均時間都為O(nlgn)。經過比較實驗，筆者選擇了快速排序法。另外，Visual C++提供的run-time庫也提供了現成的快速排序的函數qsort( )可供使用。
圖 2 基於最佳路徑計算的網路拓撲表示
Fig. 2 The Presentation of the Network Topology
Used for Computing the Shortest Path
按照以上思路，筆者用Visual C++實現了吉奧之星（GeoStar）中的最佳路徑模塊。以北京的街道為數據（共6 313個結點，9 214條弧段(雙向)），在主頻為133、硬碟為1 G、內存為32 M的機器上，計算一條貫穿全城、長為155.06 km的線路，約需1 s～2 s。如圖 3所示。
圖 3 GeoStar中最佳路徑實現示意圖
ps:圖片沒有辦法貼上去.
你可以參考《演算法導論》第二版
⑵ 蟻群演算法最佳路徑獲取
智能網聯汽車路徑規劃的蟻群演算法可以簡單地描述為：以當前網格為中心，在每隻螞蟻的起點放置m個螞蟻，根據某個策略進行選擇，然後進入下一個網格，利用本地信息更新策略更新信息素。
當第一個螞蟻k到達目標節點時，由於它首先到達並且花費的時間最少，因此在當前一輪優化中，它獲得的路徑是最優的，在k所得的路徑上執行全局信息更新並保存，此路徑是當前的最佳路徑。
⑶ 求最優路徑的演算法
以下是C寫的廣度優先的最短路徑窮舉法,希望對你有所幫助.
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
#define SIGHTS 4 //自定義景點個數為4，以後可以擴充
class Sight //景點類信息，以後可以擴充
{
public:
Sight(string name, string sd) { sname = name; sight_detial = sd; }
string Sight_Name() { return sname; }
string Sight_detial() { return sight_detial; }
protected:
string sname; //景點名稱
string sight_detial; //景點備注
};
struct SI
{
string sname; //景點名稱
int index; //景點編碼
};
SI SightInfo[SIGHTS];
map<int, string>results; //距離與路徑的映射結構體，可以動態擴充
vector<Sight> sights; //VECTOR向量保存景點信息，目前的作用只是保存
//但是其強大的功能完全可以應付以後的功能擴充
int MinDistanct = 50000; //假定最小距離為一個很大的值
string Sight_Names = "楓林園蛟橋園青山園麥廬園 "; //目標字元串
string Best_Path; //保存最佳路徑的STRING字元串
int DISTANCE[4][4] = { //查找表，用於儲存接點之間距離的信息
0, 1500, 2500, 2400,
1500, 0, 800, 0,
2500, 800, 0, 200,
2400, 0, 200, 0
};
bool connect[4][4] = { //查找表，用於儲存接點之間連通的信息
0, 1, 1, 1,
1, 0, 1, 0,
1, 1, 0, 1,
1, 0, 1, 0
};
void InitSights()
{ //初始化景點的各類信息
SightInfo[0].index=0;
SightInfo[0].sname = "麥廬園";
SightInfo[1].index=1;
SightInfo[1].sname = "楓林園";
SightInfo[2].index=2;
SightInfo[2].sname = "蛟橋園";
SightInfo[3].index=3;
SightInfo[3].sname = "青山園";
Sight s1("楓林園",
"楓林園以計算機系的理工科學生為主，是江西財經大學的唯一一個計算機學院");
sights.push_back(s1);
Sight s2("蛟橋園",
"蛟橋園是江西財經大學的會計、貿易等財務教學為主的教學樓群，為本部");
sights.push_back(s2);
Sight s3("青山園",
"青山園是江西財經大學的會計、貿易等財務教學為主的學生的宿舍群");
sights.push_back(s3);
Sight s4("麥廬園",
"麥廬園是江西財經大學的外語、藝術等人文科學為主的學習園地");
sights.push_back(s4);
}
void Find_Ways(string start, string end, int DIST, string path, int depth)
{ //遞歸調用，逐層尋找可連通的路徑，並以該路徑繼續重復循環查找，根據分析可以
//知道，所有最優解即最短路徑所經過的接點數目必定小於N，於是採用廣度優先遍歷，
//設置count為循環深度，當count大於SIGHTS時退出循環
int count = 1;
int i,j;
int start1 = 0,end1 = 0;
int distanct = 0, storeDist = 0;
string temp, target, pathway, storePath; //臨時儲存體，用於恢復遞歸調用後會
//改變的數據，以便之後無差別使用
count += depth;
if(count > SIGHTS)
return;
distanct += DIST; //距離累加
if(path=="") //第一次時，pathway初始化為第一個接點名稱
{
pathway = start;
pathway += "=>";
}
if(path!="")
pathway = path;
storeDist = distanct; //填充臨時儲存值
storePath = pathway;
for(i = 0; i < SIGHTS; ++i) //通過遍歷，查找景點名稱對應的編號
{
if(start == SightInfo[i].sname)
start1 = SightInfo[i].index;
if(end == SightInfo[i].sname)
end1 = SightInfo[i].index;
}
for(i = 0; i < SIGHTS; i++) //演算法核心步驟
{
if(connect[start1][i] != 0)
{
if(i==end1) //如果找到了一條路徑，則保存之
{
distanct += DISTANCE[start1][end1];
for(j = 0; j < SIGHTS; ++j)
{
if(end1==SightInfo[j].index)
target = SightInfo[j].sname;
}
pathway += target;
results.insert(make_pair(distanct, pathway)); //保存結果路徑信息
distanct = storeDist; //恢復數據供下次使用
pathway = storePath;
}
else //分支路徑
{
for(j = 0; j < SIGHTS; ++j)
{
if(i==SightInfo[j].index)
temp = SightInfo[j].sname;
}
pathway += temp;
pathway += "=>";
distanct += DISTANCE[start1][i];
Find_Ways(temp, end, distanct, pathway, count); //以該連通的分支
//路徑繼續遞歸調用，查找子層路徑信息。
distanct = storeDist; //恢復數據
pathway = storePath;
}
}
}
}
void Find_Best_Way()
{ //該函數建立在上述函數執行完畢之後，在map映射結構中通過對比每條路徑的長度，來
//選擇最優解
map<int, string>::iterator itor = results.begin();
while(itor!=results.end()) //尋找最小值
{
// cout<<"distanct = "<<itor->first<<endl;
if(itor->first < MinDistanct)
MinDistanct = itor->first;
itor++;
}
itor = results.begin();
while(itor!=results.end()) //尋找最小值所對應的整個路徑字元串
{
if(itor->first == MinDistanct)
Best_Path = itor->second;
itor++;
}
}
int main(int argc, char *argv[])
{
int choice;
size_t t1=0,t2=0;
string source, termination;
InitSights();
do{
cout<<"////////////////////////////////////////////////////////\n"
<<"**** 請輸入您所需要的服務號碼: ********\n"
<<"**** 1.楓林園介紹 ********\n"
<<"**** 2.蛟橋園介紹 ********\n"
<<"**** 3.青山園介紹 ********\n"
<<"**** 4.麥廬園介紹 ********\n"
<<"**** 5.查詢地圖路徑 ********\n"
<<"**** 6.退出查詢系統 ********\n"
<<"////////////////////////////////////////////////////////\n"
<<endl;
cin>>choice;
switch(choice)
{
case 1:
cout<<sights[0].Sight_Name()<<endl
<<sights[0].Sight_detial()<<endl;
break;
case 2:
cout<<sights[1].Sight_Name()<<endl
<<sights[1].Sight_detial()<<endl;
break;
case 3:
cout<<sights[2].Sight_Name()<<endl
<<sights[2].Sight_detial()<<endl;
break;
case 4:
cout<<sights[3].Sight_Name()<<endl
<<sights[3].Sight_detial()<<endl;
break;
case 5:
flag1:
cout<<"請輸入路徑的起點"<<endl;
cin>>source;
cout<<"請輸入路徑的終點"<<endl;
cin>>termination;
if((t1=Sight_Names.find(source,t1))==string::npos || (t2=Sight_Names.find(termination,t2))==string::npos)
{ //檢查輸入的數據是否含有非法字元
cerr<<"輸入的路徑結點不存在，請重新輸入:"<<endl;
goto flag1;
}
Find_Ways(source, termination, 0, "",0); //尋找所有可能解
Find_Best_Way(); //在所有可能解中找到最優解
cout<<"最佳路徑是："<< Best_Path <<endl
<<"最小路程為(米):"<< MinDistanct<<endl;
t1 = 0; //恢復字元串下標，以支持下次查詢
t2 = 0;
break;
case 6:
break;
default:
cerr<<"您的選擇超出了范圍，請重新輸入:"<<endl;
break;
}
}while(choice!=6);
system("pause");
return 0;
}
⑷ BGP協議最佳路徑的選擇演算法有哪些
每個BGP路由器通過鄰居聲名與周邊的一個或多個路由器連接。一旦建立了鄰居關系，這些BGP路由器之間就會相互交換路由信息。據我最近一次統計，整個互聯網上有大約12.5萬個路由信息，因此要配備一個強大的路由器才能將所有BGP路由信息接收下來。
由於整個互聯網的BGP路由表有超過20萬個路由，同時一個BGP路由器可能從多個來源收到多份的路由表，因此肯定會有一種方法可以比較不同的BGP路由表，並從中選擇最佳的路由方案。這種方法就是BGP最佳路徑選擇演算法。
可能你會注意到，CiscoBGP路由器會將應用權重（weight）作為路由表的第一標准，而其它品牌的路由器則不是這樣。Cisco的官方BGP最佳路徑選擇演算法文檔中詳細列明了所參考的各項標准。接下來我會列出每種標准並給出解釋和範例。
默認情況下，BGP最佳路徑都是基於最短自治系統（AS）的原理得出的。不過很多時候，諸如weight，localpreference以及MED這樣的標准都是網路管理員自行設定的。
接下來我們就按照BGP選擇最佳路徑的參考順序將這幾項標准介紹一下：
#1 Weight —權重是Cisco為本地路由器設定的自定義參數，並不隨路由器更新而變化。如果指向某一IP地址的路徑有多條（這很常見），那麼BGP會尋找權重最高的路徑。設定權重的參考因素很多，包括鄰居命令，as-path訪問列表，或者路由鏡像等。
#2 Local Preference — 本地出口優先順序參數會告知AS哪條路徑具有本地優先，數值越高優先順序越高。默認為100。比如：
bgp default local-preference 150
#3 Network or Aggregate—這個參數會選擇本地發起的網路或聚合作為路徑。將特定的路徑加入路由中，會讓路由更有效率，同時也節省了網路空間。更多有關聚合的信息，可以參考Cisco的文章「UnderstandingRouteAggregation in BGP.」
#4 Shortest AS_PATH — BGP 只有在weight， localpreference和locallyoriginated相當接近的時候才使用這個參數。
#5 Lowest origin type — 這個參數處理Interior Gateway Protocol（IGP）協議的優先順序低於 Exterior Gateway Protocol （EGP）協議。
#6 Lowest multi-exit discriminator （MED） — 較低的MED值要優於較高的MED值。
#7 eBGP over iBGP — 類似於#5， BGP AS Path 更傾向 eBGP 而不是 iBGP。
#8 Lowest IGP metric — 這個參數傾向於採用最低IGP作為BGP下一跳。
#9 Multiple paths — 這個參數決定是否要在路由表中裝入多個路徑。可以參考 BGPMultipath獲取更多信息。
#10 External paths — 當所有路徑都為外部路徑時，選擇首先接收到的路徑（較老的路徑）。
#11 Lowest router ID — 選擇來自具有最低路由器ID的BGP路由器的路徑。
#12 Minimum cluster list — 如果多個路徑的originator或路由器ID相同，選擇cluster列表長度最短的路徑。
⑸ 最短路徑演算法
Dijkstra演算法，A*演算法和D*演算法
Dijkstra演算法是典型最短路演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法能得出最短路徑的最優解，但由於它遍歷計算的節點很多，所以效率低。
Dijkstra演算法是很有代表性的最短路演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。
Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 演算法和 D* 演算法表述一致，這里均採用OPEN,CLOSE表的方式。
大概過程：
創建兩個表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
1． 訪問路網中里起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。
2． 從OPEN表中找出距起始點最近的點，找出這個點的所有子節點，把這個點放到CLOSE表中。
3． 遍歷考察這個點的子節點。求出這些子節點距起始點的距離值，放子節點到OPEN表中。
4． 重復2，3，步。直到OPEN表為空，或找到目標點。
提高Dijkstra搜索速度的方法很多，常用的有數據結構採用Binary heap的方法，和用Dijkstra從起始點和終點同時搜索的方法。
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))；這樣估價函數f在g值一定的情況下，會或多或少的受估價值h的制約，節點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優於Dijstra演算法的毫無無方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索過程：
創建兩個表，OPEN表保存所有已生成而未考察的節點，CLOSED表中記錄已訪問過的節點。
遍歷當前節點的各個節點，將n節點放入CLOSE中，取n節點的子節點X,->算X的估價值->
While(OPEN!=NULL)
{
從OPEN表中取估價值f最小的節點n;
if(n節點==目標節點) break;
else
{
if(X in OPEN) 比較兩個X的估價值f //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於OPEN表的估價值 )
更新OPEN表中的估價值; //取最小路徑的估價值
if(X in CLOSE) 比較兩個X的估價值 //注意是同一個節點的兩個不同路徑的估價值
if( X的估價值小於CLOSE表的估價值 )
更新CLOSE表中的估價值; 把X節點放入OPEN //取最小路徑的估價值
if(X not in both)
求X的估價值;
並將X插入OPEN表中; //還沒有排序
}
將n節點插入CLOSE表中;
按照估價值將OPEN表中的節點排序; //實際上是比較OPEN表內節點f的大小，從最小路徑的節點向下進行。
}
A*演算法和Dijistra演算法的區別在於有無估價值，Dijistra演算法相當於A*演算法中估價值為0的情況。
動態路網，最短路演算法 D*A* 在靜態路網中非常有效（very efficient for static worlds），但不適於在動態路網，環境如權重等不斷變化的動態環境下。
D*是動態A*（D-Star,Dynamic A*） 卡內及梅隆機器人中心的Stentz在1994和1995年兩篇文章提出，主要用於機器人探路。是火星探測器採用的尋路演算法。
主要方法：
1.先用Dijstra演算法從目標節點G向起始節點搜索。儲存路網中目標點到各個節點的最短路和該位置到目標點的實際值h,k（k為所有變化h之中最小的值,當前為k=h。每個節點包含上一節點到目標點的最短路信息1(2),2(5),5(4)，4（7）。則1到4的最短路為1-2-5-4。
原OPEN和CLOSE中節點信息保存。
2.機器人沿最短路開始移動，在移動的下一節點沒有變化時，無需計算，利用上一步Dijstra計算出的最短路信息從出發點向後追述即可，當在Y點探測到下一節點X狀態發生改變，如堵塞。機器人首先調整自己在當前位置Y到目標點G的實際值h(Y)，h(Y)=X到Y的新權值c(X,Y)+X的原實際值h(X).X為下一節點(到目標點方向Y->X->G），Y是當前點。k值取h值變化前後的最小。
3.用A*或其它演算法計算，這里假設用A*演算法,遍歷Y的子節點，點放入CLOSE,調整Y的子節點a的h值，h(a)=h(Y)+Y到子節點a的權重C(Y,a),比較a點是否存在於OPEN和CLOSE中，方法如下：
while()
{
從OPEN表中取k值最小的節點Y;
遍歷Y的子節點a,計算a的h值 h(a)=h(Y)+Y到子節點a的權重C(Y,a)
{
if(a in OPEN) 比較兩個a的h值
if( a的h值小於OPEN表a的h值 )
{ 更新OPEN表中a的h值;k值取最小的h值
有未受影響的最短路經存在
break;
}
if(a in CLOSE) 比較兩個a的h值 //注意是同一個節點的兩個不同路徑的估價值
if( a的h值小於CLOSE表的h值 )
{
更新CLOSE表中a的h值; k值取最小的h值;將a節點放入OPEN表
有未受影響的最短路經存在
break;
}
if(a not in both)
將a插入OPEN表中; //還沒有排序
}
放Y到CLOSE表；
OPEN表比較k值大小進行排序；
}
機器人利用第一步Dijstra計算出的最短路信息從a點到目標點的最短路經進行。
D*演算法在動態環境中尋路非常有效，向目標點移動中，只檢查最短路徑上下一節點或臨近節點的變化情況，如機器人尋路等情況。對於距離遠的最短路徑上發生的變化，則感覺不太適用。