#include <iostream> using namespace std; const int inf=1000; int s[100],t[100]; int map[100][100];int v,n;void dijkstra() { s[1]=0,t[1]=0; //使用零來實現(xiàn)也是可以的。 for(int i=2;i<=v;i++) s[i]=map[1][i]; //不斷的進行松弛。 for(int i=2;i<=v;i++) { //首先是選擇距離頂點一最小的那一個頂點的。 int themin=inf; int flag; for(int j=2;j<=v;j++) //使用的是s[]，只能是用一個的。 { if(t[j]!=0&&s[j]<themin) //只是用t【i】來標志是不是加上了。用來表示其中的具體含義。 { themin=s[j]; flag=j; } } t[flag]=0; //一個是標志，另一個是結果。 for(int j=1;j<=v;j++) //清楚所代表的意思就行了。 { if(t[j]!=0&&map[flag][j]+s[flag]<s[j]) //應該是已經(jīng)進行了遍歷。 { s[j]=s[flag]+map[flag][j]; //選擇s【j】中最短的。 } } } for(int i=1;i<=v;i++) cout<<s[i]<<" "; cout<<endl; } int main() { cout<<"請輸入頂點數(shù)(從一開始)"<<endl; cin>>v; cout<<"請輸入邊數(shù)"<<endl; cin>>n; cout<<"請輸入每條邊的長度。(如果沒有直接到達的是inf)"<<endl; for(int i=0;i<=v;i++) //初始化應該在輸入之前。太早和太完都是不行的。 for(int j=0;j<=v;j++) { map[i][j]=inf; s[i]=inf; t[i]=inf; //t[i]僅僅只是一個標志罷了。 if(i==j) map[i][j]=0; } for(int i=1;i<=n;i++) { int a,b; cin>>a>>b; cin>>map[a][b]; } dijkstra(); return 0; }

?

總結

以上是生活随笔為你收集整理的Dijkstra算法实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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