1.概述：Dijkstra算法是用來尋找兩點(diǎn)之間最短路徑的算法，在實(shí)際生活中有著很大的作用他的思想就是選定一點(diǎn)然后向后遍歷直至所有點(diǎn)到選定點(diǎn)的最短距離全部求處為止。
2.算法思想：
（1）初始化：先找處從源點(diǎn)V0到各終點(diǎn)Vk的直達(dá)路徑（V0,Vk），即通過一條弧到達(dá)的路徑。
（2）選擇：從這些路徑中找出一條長度最短的路徑（V0,u）。
（3）更新：然后對(duì)其余各條路徑進(jìn)行適當(dāng)?shù)恼{(diào)整：
若在圖中存在弧（u，Vk），且（u，Vk）+（V0,u）<（V0,Vk），則以路徑（V0,u,Vk）代替（V0,Vk）。

（4）在調(diào)整后的各條路徑中，再找長度最短的路徑，以此類推。
代碼及注釋如下：
3.算法實(shí)現(xiàn)圖示：

1.數(shù)據(jù)結(jié)構(gòu)及其初始化：

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm>#define N 100 #define INITFITE 32767 using namespace std;typedef struct Node{int vernum,arcnum;char data[N];int martrix[N][N]; }Graph;struct NNode{int pree; //存儲(chǔ)該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)！int lowcost;//存儲(chǔ)到該節(jié)點(diǎn)的最短路程！ }closedge[N];int locate(Graph G,char ch) {int i;for (int i = 0;i < G.vernum;i++){if (G.data[i] == ch)return i;} }

2.鄰接矩陣的建立：

void create_Graph(Graph &G) {char v1,v2;int weight;cout<<"please key in the vernum & arcnum"<<endl;cin>>G.vernum>>G.arcnum;cout<<"please key in all the vertexs"<<endl;for (int i = 0;i < G.vernum;i++)cin>>G.data[i];cout<<"please key in the v1 & v2 & weight"<<endl;for (int i = 0;i < G.vernum;i++)for (int j = 0;j < G.vernum;j++)G.martrix[i][j] = INITFITE;for (int ii = 0;ii < G.arcnum;ii++){cin>>v1>>v2>>weight;int i = locate(G,v1);int j = locate(G,v2);G.martrix[i][j] = weight;} }

3.Dijkstra算法及顯示路徑函數(shù)：

bool visited[N]; void DIJ(Graph G,char ch) {int v = locate(G,ch);//找到源點(diǎn)在字符數(shù)組中的位置int w;visited[v] = true;closedge[v].pree = -1;//源點(diǎn)的前驅(qū)置成-1；int min = 1000000;for (int i = 0;i < G.vernum;i++)//----------初始化{ closedge[i].lowcost = G.martrix[v][i];if (!visited[i]){if (closedge[i].lowcost < INITFITE) //如果成立，則說明有直達(dá)邊。closedge[i].pree = v;//則將前驅(qū)置成v;else //否則沒有直達(dá)邊closedge[i].pree = -1;//則將前驅(qū)置成-1；if (closedge[i].lowcost < min) //尋找最小的邊！！{w = i;min = closedge[i].lowcost;}}cout<<closedge[i].lowcost<<endl; //打印初始化后的到各點(diǎn)的最短距}cout<<"----------------"<<endl; closedge[w].pree = v;for (int j = 0;j < G.vernum - 1;j++) //---------更新{v = w;visited[v] = true; //已經(jīng)確定的點(diǎn)置成true；min = 1000000;for (int i = 0;i < G.vernum;i++){ if (!visited[i]){if (closedge[v].lowcost + G.martrix[v][i] < closedge[i].lowcost) // 如果由于D.data[v]的引入導(dǎo)致到G.data[i]的距離改變，則將最短路徑賦成改變后的新值，將前驅(qū)賦成v；{closedge[i].lowcost = closedge[v].lowcost + G.martrix[v][i];closedge[i].pree = v; }if (closedge[i].lowcost < min) //找到最小的邊{w = i;min = closedge[i].lowcost;}}//cout<<"&&"<<closedge[i].pree<<endl;cout<<closedge[i].lowcost<<endl;//打印該次更新后的情況} cout<<"----------------"<<endl; //cout<<min<<endl;//closedge[w].pree = v;//closedge[w].lowcost = min;} }void show(Graph G,char ch) {int v = locate(G,ch);char ans[N];int j,k;for (int i = 0;i < G.vernum;i++){memset(ans,0,sizeof(ans));//cout<<closedge[i].pree<<endl;k = i;if (closedge[i].pree == -1 && i != v){cout<<ch<<"--->"<<G.data[i]<<":";cout<<"There is no way"<<" "<<closedge[i].lowcost<<endl;continue;}else if (closedge[i].pree == -1 && i == v){cout<<ch<<"--->"<<G.data[i]<<":";cout<<G.data[v]<<" "<<G.data[v]<<" "<<0<<endl;continue;}else{j = 0;ans[j] = G.data[k];while (closedge[k].pree != v) //媽耶 問題出在這里 調(diào)了半天 小循環(huán)不要與外邊的循環(huán)控制變量一樣！！！此處控制條件十分巧妙！ {ans[++j] = G.data[closedge[k].pree];k = closedge[k].pree;}ans[++j] = G.data[v];}for (int i1 = 0;i1 <= j / 2;i1++)//導(dǎo)致得到的序列{swap(ans[i1],ans[j - i1]);}cout<<ch<<"--->"<<G.data[i]<<":";for (int i2 = 0;i2 <= j;i2++){cout<<ans[i2]<<" ";}cout<<closedge[i].lowcost<<endl;//cout<<endl;} }

4.主函數(shù)：

int main(){Graph G;create_Graph(G);for (int i = 0;i < G.vernum;i++){for (int j = 0;j < G.vernum;j++)printf ("%7d ",G.martrix[i][j]);cout<<endl;}memset(visited,false,sizeof(visited));DIJ(G,'B');show(G,'B');return 0; } /*A C 10 A F 100 A E 30 B C 5 C D 50 D F 10 E D 20 E F 60*/

例：（求B點(diǎn)到其他點(diǎn)的最短路徑）

運(yùn)行結(jié)果：

迪杰斯特拉算法是求某一個(gè)點(diǎn)到其他點(diǎn)的最短距離的算法，考研要求掌握！！而各點(diǎn)到其他點(diǎn)的最短距離的算法是弗洛伊德算法，考研要求沒有那么嚴(yán)格！但是要求會(huì)手工操作！

總結(jié)

以上是生活随笔為你收集整理的迪杰斯特拉算法详解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。