Dijkstra
用来计算从一个点到其他所有点的最短路径的算法，是一种单源最短路径算法。也就是说，只能计算起点只有一个的情况。Dijkstra的时间复杂度是O (|v|^2)，它不能处理存在负边权的情况。
邻接矩阵存图
#include<iostream>
using namespace std;
//最短路径——Djikstra算法
// 求单元最短路
// 时间复杂度：O(n^2)
//求最短路径：BFS、Floyd(基于dp)、Djikstra算法
//以 邻接矩阵 存 带权无向图 为例
#define INF 68888
int 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的邻接点 修改dist
for (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
#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
#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;
}