?

#include <iostream> #define INF 9999999 using namespace std;int main() {int e[51][51],book[50],dis[50],s,t,d,n,m;//n個(gè)城市，m條路cin>>n>>m;for(int i=1;i<=50;i++){for(int j=1;j<=50;j++){if(j!=i){e[i][j]=INF;}else e[i][j]=0;}}for(int i=1;i<=m;i++){cin>>s>>t>>d;e[t][s]=e[s][t]=d;}for(int i=1;i<=n;i++){dis[i]=e[1][i];book[i]=0;}book[1]=1;int min=INF,j;for(int i=1;i<=n;i++){for(int k=1;k<=n;k++){if(dis[k]<min&&!book[k]){min=dis[k];j=i;}}
book[j]=1;for(int i=1;i<=n;i++){if(dis[i]>dis[j]+e[j][i]){dis[i]=dis[j]+e[j][i];}}}cout<<" ";for(int i=1;i<=n;i++)cout<<i<<" ";cout<<endl<<1<<" ";for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<e[i][j]<<" ";}cout<<endl<<i+1<<" ";}return 0; }

?

?

?

#include <iostream> #include <cstring> #include <queue> #include <cstdlib> #include <stdio.h> #define MAX 15000 #define INF 9999999 using namespace std; class Edge{ public:int u,v,w,next; }edge[MAX]; int head[MAX]; int d[MAX]; int num=0; bool visit[MAX]; int n,ml,md,a,b,dis,m; struct cmp {bool operator()(int a,int b){return d[a]>d[b];} }; priority_queue<int,vector<int>,cmp> q; void dijkstra() {for(int i=1;i<n+1;i++)//i=n 忘了初始化！！！！！！！！！！！{d[i]=INF;visit[i]=false;}q.push(1);d[1]=0;while(!q.empty()){int u=q.top();q.pop(); visit[u]=true;for(int e=head[u];e!=-1;e=edge[e].next){int v=edge[e].v;int w=edge[e].w;if(!visit[v]&&d[v]>d[u]+w){d[v]=d[u]+w;q.push(v);}}}}void addEdge(int x,int y,int z) {edge[num].u=x;edge[num].v=y;edge[num].w=z;edge[num].next=head[x];head[x]=num++; } int main() {while(cin>>n>>m){if(n==0&&m==0) break;memset(head,-1,sizeof(head)); num=0;for(int i=1;i<=m;i++){cin>>a>>b>>dis;addEdge(a,b,dis);addEdge(b,a,dis);}dijkstra();cout<<d[n]<<endl;}return 0; }

根據(jù)spfa改，不知道為啥TE了， ...因?yàn)橥浢看窝h(huán)將num=0 ，T_T 要注意是雙向邊，所以要加兩次addEdge。

?

dijkstra 尋找最短路

prim最小生成樹(shù)

雖然兩者似乎看起來(lái)差不多（都是利用了貪心思想，找到最近的一點(diǎn)），但是更新的東西是完全不一樣的?

轉(zhuǎn)載于:https://www.cnblogs.com/LandingGuy/p/9280285.html

總結(jié)

以上是生活随笔為你收集整理的Dijkstra 最短路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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