Dijkstra

用來計算從一個點到其他所有點的最短路徑的算法，是一種單源最短路徑算法。也就是說，只能計算起點只有一個的情況。Dijkstra的時間復雜度是O (|v|^2)，它不能處理存在負邊權的情況。

鄰接矩陣存圖

#include<iostream>
using namespace std;//最短路徑——Djikstra算法
// 求單元最短路
// 時間復雜度：O(n^2)
//求最短路徑：BFS、Floyd(基于dp)、Djikstra算法//以 鄰接矩陣 存 帶權無向圖 為例#define INF 68888int g[105][105];
int dist[105];//記錄最短路的大小
int path[105];//記錄最短路的順序
int flag[105];//flag[i]=1 i的最短路已確定  =0未確定
int n, m;
int s;//起點void Djikstra(int s) {//起點到起點flag[s] = 1;dist[s] = 0;path[s] = s;//其他點到起點int minn = INF;//最小的dist的值int t=0;//最小的dist的下標for (int i = 1; i < n; i++) {//循環n-1次minn = INF;for (int j = 0; j < n; j++) {if (flag[j] == 0 && dist[j] < minn) {minn = dist[j];t = j;}}//t點時dist值最小的點flag[t] = 1;//變為已確定最短路徑的點//t去中轉t的鄰接點 修改distfor (int j = 0; j < n; j++) {if (flag[j] == 0 && dist[j] > (dist[t] + g[t][j])) {dist[j] = dist[t] + g[t][j];path[j] = t;}}}
}int main() {cin >> n >> m;//初始化for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j) {g[i][j] = 0;}else {g[i][j] = INF;}}}int x, y, w;for (int i = 1; i <= m; i++) {cin >> x >> y >> w;g[x][y] = g[y][x] = w;}cin >> s;//初始化for (int i = 0; i < n; i++) {dist[i] = g[s][i];if (g[s][i] == INF) {path[i] = -1;}else {path[i] = s;}}Djikstra(s);//輸出驗證for (int i = 0; i < n; i++) {cout << "s到" << i << "的最短路徑長度是" << dist[i] <<":";//倒敘輸出路徑cout << i << " ";int j = i;while (path[j] != j) {cout << path[j] << " ";j = path[j];}cout << endl;}return 0;
}

鏈式前向星版本

#include<bits/stdc++.h>
using namespace std;
#define inf 1001 //鏈式前向星寫Dijkstra 
int n,m,cnt; //n<100 0<權值<1000
int h[105];
struct Edge{int to,w,next;
}e[10005]; //100個點 最多100*（100-1）條邊 
int dis[105],v[105]; void add(int u,int v,int w){e[cnt].to=v;e[cnt].w=w;e[cnt].next=h[u]; h[u]=cnt;cnt++;
}void dij(int x){for(int i=1;i<=n;++i) {dis[i]=inf;}dis[x]=0;int u; for(int j=1;j<=n;++j){int minn=inf,k=-1;for(int i=1;i<=n;++i){if(v[i]==0&&dis[i]<minn){minn=dis[i];k=i;}	} v[k]=1;for(int i=h[k];i!=-1;i=e[i].next){u=e[i].to;if(v[u]==0&&dis[u]>dis[k]+e[i].w){dis[u]=dis[k]+e[i].w; }}}
}int main(){memset(h,-1,sizeof h);cin>>n>>m;int x,y,w; for(int i=1;i<=m;++i){cin>>x>>y>>w;//有向圖add(x,y,w); } cin>>x;dij(x);for(int i=1;i<=n;++i){cout<<dis[i]<<" ";}return 0;
} 

優化版本：堆 找最小的點 ------> 優先隊列

#include<bits/stdc++.h>
using namespace std;
#define inf 1001 //鏈式前向星寫Dijkstra 
int n,m,cnt; //n<100 0<權值<1000
int h[105];
struct Edge{int to,w,next;
}e[10005]; //100個點 最多100*（100-1）條邊 
int dis[105],v[105]; 
typedef pair<int,int> PII; 
priority_queue<PII,vector<PII>,greater<PII>> q; void add(int u,int v,int w){e[cnt].to=v;e[cnt].w=w;e[cnt].next=h[u]; h[u]=cnt;cnt++;
}void dij(int x){//堆優化 for(int i=1;i<=n;++i) {dis[i]=inf;}dis[x]=0;PII now;now.first=dis[x];now.second=x;q.push(now);while(q.size()){now=q.top();q.pop();int minn=now.first;int k=now.second;if(v[k]==1) continue;//避免重復入隊的點v[k]=1;for(int i=h[k];i!=-1;i=e[i].next){int u=e[i].to;if(dis[u]>minn+e[i].w){dis[u]=minn+e[i].w;now.first=dis[u];now.second=u;q.push(now); }}}
}int main(){memset(h,-1,sizeof h);cin>>n>>m;int x,y,w; for(int i=1;i<=m;++i){cin>>x>>y>>w;//有向圖add(x,y,w); } cin>>x;dij(x);for(int i=1;i<=n;++i){cout<<dis[i]<<" ";}return 0;
} 

例題

1

P4779 【模板】單源最短路徑（標準版） - 洛谷

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9 
using ll=long long ;//鏈式前向星寫Dijkstra 
int n,m,cnt; //n<100 0<權值<1000
int h[100005];
struct Edge{int to,w,next;
}e[200005]; //100個點 最多100*（100-1）條邊 
ll dis[100005];
int v[100005]; 
typedef pair<int,int> PII; 
priority_queue<PII,vector<PII>,greater<PII>> q; void add(int u,int v,int w){e[cnt].to=v;e[cnt].w=w;e[cnt].next=h[u]; h[u]=cnt;cnt++;
}void dij(int x){//堆優化 for(int i=1;i<=n;++i) {dis[i]=inf;}dis[x]=0;PII now;now.first=dis[x];now.second=x;q.push(now);while(q.size()){now=q.top();q.pop();int minn=now.first;int k=now.second;if(v[k]==1) continue;v[k]=1;for(int i=h[k];i!=-1;i=e[i].next){int u=e[i].to;if(dis[u]>minn+e[i].w){dis[u]=minn+e[i].w;now.first=dis[u];now.second=u;q.push(now); }}}
}int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);memset(h,-1,sizeof h);int s;//scanf("%d %d %d",&n,&m,&s);cin>>n>>m>>s; int x,y,w; for(int i=1;i<=m;++i){//scanf("%d %d %d",&x,&y,&w);cin>>x>>y>>w;add(x,y,w); } dij(s);for(int i=1;i<=n;++i){//printf("%d ",dis[i]);cout<<dis[i]<<" ";}return 0;
} 

2

[P8802 藍橋杯 2022 國 B] 出差 - 洛谷

#include<bits/stdc++.h>
using namespace std;
using ll=long long ;
int n,m,cnt;
int h[1005],c[1005];
int flag[1005];//標記數組 
struct Edge{int to,w,next;
}e[20005];//無向圖開兩倍空間
int dis[1005]; 
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII>> q;
void add(int u,int v,int w){e[cnt].to=v;e[cnt].w=w;e[cnt].next=h[u];h[u]=cnt;cnt++;
}void dij(int s){dis[s]=0;PII now,next;int u,v,w;now.first=dis[s];now.second=s;q.push(now);while(!q.empty()){now=q.top();q.pop();u=now.second;if(flag[u]==1) continue;flag[u]=1;for(int i=h[u];i!=-1;i=e[i].next){v=e[i].to;w=e[i].w;if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;next.first=dis[v];next.second=v;q.push(next);}}} 
}int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m;memset(h,-1,sizeof h); memset(dis,0x3f,sizeof dis);//dis[i]=0x3f3f3f3f按字節賦值 for(int i=1;i<=n;++i){cin>>c[i];}int u,v,w;for(int i=1;i<=m;++i){cin>>u>>v>>w;add(u,v,w+c[v]);//u---->v   點權加入邊權里 add(v,u,w+c[u]);//v---->u}dij(1);cout<<dis[n]-c[n]<<endl; //最后減去終點點權 return 0;
} 

3

P1462 通往奧格瑞瑪的道路 - 洛谷

#include<bits/stdc++.h>
using namespace std;
using ll=long long ;
int n,m,b,cnt=0;
int h[10005],f[10005];
int flag[10005];//標記數組 
struct Edge{int to,w,next;
}e[100005];//無向圖開兩倍空間
int dis[10005]; 
typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII>> q;
void add(int u,int v,int w){e[cnt].to=v;e[cnt].w=w;e[cnt].next=h[u];h[u]=cnt;cnt++;
}bool dij(int s,int maxx){if(maxx<f[s]) return false; memset(dis,0x3f,sizeof dis);memset(flag,0,sizeof flag);PII now,next;int u,v,w;dis[s]=0;now.first=dis[s];now.second=s;q.push(now);while(!q.empty()){now=q.top();q.pop();u=now.second;if(flag[u]==1) continue;flag[u]=1;for(int i=h[u];i!=-1;i=e[i].next){v=e[i].to;w=e[i].w;if(f[v]<=maxx&&dis[v]>dis[u]+w){dis[v]=dis[u]+w;next.first=dis[v];next.second=v;q.push(next);}}} return dis[n]<=b;
}int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n>>m>>b;memset(h,-1,sizeof h); int l=0x3f3f3f3f,r=-0x3f3f3f3f; for(int i=1;i<=n;++i){cin>>f[i];r=max(r,f[i]);l=min(l,f[i]);}int u,v,w;for(int i=1;i<=m;++i){cin>>u>>v>>w;if(u==v) continue;//有自環 add(u,v,w);add(v,u,w);}if(dij(1,0x3f3f3f3f)==0){cout<<"AFK"<<endl;return 0;}//二分求答案int mid=0,ans=0;while(l<=r){mid=(l+r)/2;if(dij(1,mid)){ans=mid;r=mid-1;}else{l=mid+1;}} cout<<ans<<endl;return 0;
}