單源最短路徑 迪杰斯特拉算法
1.初始化地圖，map[i][j]記錄城鎮(zhèn) i，j之間最短的道路長度，
若無道路連通 ，則為極大值
2.從起始城鎮(zhèn)開始，用廣度優(yōu)先搜索思想，嵌入松弛處理算法，
用dis[i]記錄起始城鎮(zhèn)到城鎮(zhèn) i 的最短路徑長度；

3.答案位于dis[t]，即終點(diǎn)t城鎮(zhèn)到起始城鎮(zhèn)的最小距離

#include<stdio.h> #include<queue> #define inf 10000000 using namespace std; int main(){int n,m;int map[200][200];//map[i][j]記錄城鎮(zhèn) i 到 j 間最短連通道路長度int s,t;//記錄起始村莊和終點(diǎn)村莊的編號int dis[200];//記錄 i 號村莊到起始村莊的最短路徑長度int x,y,d;int i,j;while(scanf("%d%d",&n,&m)!=EOF){for(i=0;i<n;i++)for(j=0;j<n;j++)map[i][j]=inf;//所有路徑初始化為最大值while(m--){scanf("%d%d%d",&x,&y,&d);if(map[x][y]>d)map[x][y]=d,map[y][x]=d;} scanf("%d%d",&s,&t);queue<int> q;q.push(s);//起點(diǎn)入隊(duì)for(i=0;i<n;i++) dis[i]=inf;//所有城鎮(zhèn)到起始位置的距離初始化為最大值dis[s]=0;//起始城鎮(zhèn)到其自身的距離為0//所有與起始城鎮(zhèn)連接都遍歷完了，結(jié)束遍歷 while(!q.empty()) {x=q.front();q.pop();for(i=0;i<n;i++){if(map[x][i]!=inf){//從城鎮(zhèn) x 到城鎮(zhèn) i 的路徑（到起始城鎮(zhèn)）較短 if(dis[i]>dis[x]+map[x][i]){dis[i]=dis[x]+map[x][i];//跟新 i 城鎮(zhèn)到起始城鎮(zhèn)的最短距離q.push(i); }}} }if(dis[t]==inf)printf("-1\n");elseprintf("%d\n",dis[t]);} return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu 1874 Dijkstra算法模板的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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