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表為空，或找到目標點。 #include<iostream>#include<vector>using?namespace?std;void?dijkstra(const?int?&beg,//出發點?const?vector<vector<int>?>?&adjmap,//鄰接矩陣，通過傳引用避免拷貝?vector<int>?&dist,//出發點到各點的最短路徑長度?vector<int>?&path)//路徑上到達該點的前壹個點//負邊被認作不聯通//福利：這個函數沒有用任何全局量，可以直接復制！{const?int?&NODE=adjmap.size();//用鄰接矩陣的大小傳遞頂點個數，減少參數傳遞dist.assign(NODE,-1);//初始化距離為未知path.assign(NODE,-1);//初始化路徑為未知vector<bool>?flag(NODE,0);//標誌數組，判斷是否處理過dist[beg]=0;//出發點到自身路徑長度為0while(1){int?v=-1;//初始化為未知for(int?i=0;?i!=NODE;?++i)if(!flag[i]&&dist[i]>=0)//尋找未被處理過且if(v<0||dist[i]<dist[v])//距離最小的點v=i;if(v<0)return;//所有聯通的點都被處理過flag[v]=1;//標記for(int?i=0;?i!=NODE;?++i)if(adjmap[v][i]>=0)//有聯通路徑且if(dist[i]<0||dist[v]+adjmap[v][i]<dist[i])//不滿足三角不等式{dist[i]=dist[v]+adjmap[v][i];//更新path[i]=v;//記錄路徑}}}int?main(){int?n_num,e_num,beg;//含義見下cout<<輸入點數、邊數、出發點：;cin>>n_num>>e_num>>beg;vector<vector<int>?>?adjmap(n_num,vector<int>(n_num,-1));//默認初始化鄰接矩陣for(int?i=0,p,q;?i!=e_num;?++i){cout<<輸入第<<i+1<<條邊的起點、終點、長度（負值代表不聯通）：;cin>>p>>q;cin>>adjmap[p][q];}vector<int>?dist,path;//用於接收最短路徑長度及路徑各點dijkstra(beg,adjmap,dist,path);for(int?i=0;?i!=n_num;?++i){cout<<beg<<到<<i<<的最短距離為<<dist[i]<<，反向打印路徑：;for(int?w=i;?path[w]>=0;?w=path[w])cout<<w<<<-;cout<<beg<<'\n';}}