Dijkstra基础算法

题目

1. P4779
2. P3371
3. P1339
4. P1821

如图，求 点1 ——>点4 的最短路

<im

1. 先定义一个dis数组
2. 松驰：对于一条从u到v，长度为w的连边，若dis[u]+w<dis[v],则令dis[v]=dis[u]+w
3. 再从已记录的点中找出dis值最小的点，搜索其出边，松弛
4. 重复2，3具体步骤与代码

具体步骤与代码

1. 将起始点dis置0
2. 选择当前未标记的殿中dis值最小的一个
3. 对该点所有连边进行松弛操作
4. 对该点进行标记
5. 重复2，3，4步，知道不存在一条从已标记点通向未标记点的连边

建边

​ 这里采用链式前向星存图

​ 也是一种邻接表，原理是将每个点出发的所有边以链表的形式存下

struct L{
    int to,next,length;
}bian[maxn];
int head[maxn],k;
void(int u,int v,int w){
    bian[++k].to=v;
    bian[k].length=w;
    bian[k].next=head[u];//下一条边
    head[u]=k;//下标
}

优先队列——优化（用来维护dis最小的点）

struct P{
	int dis,id;//id即点的序号
	bool operator < (const P &that) const{
		return dis>that.dis;//注意：优先队列要反着写
	}
};
priority_queue<P> q;

Dijkstra主代码

bool vis[maxn];
int n;
int s;//起点
int dijkstra(){
    for(int i=0;i<+n;i++)dis[i]=inf;
    dis[s]=0;
    q.push((P){0,s});//注意:这里第一个位对应dis，第二个位对应id
    while(!q.empty()){
        int u=q.top().id;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=bian[i].next){
            int v=bian[i].to;
            if(dis[v]>dis[u]+bian[i].length){
                dis[v]=dis[u]+bian[i].length;
                q.push((P){dis[v],v});
            }
        }
	}
}

总代码

#include<bits/stdc++.h>
using namespace std;
int inf=9999999;
int maxn=10010;
int n,m,s,head[maxn],k;
bool vis[maxn];
struct P{
	int dis,id;
	bool operator < (const P &that) const{
		return dis>that.dis;
	}
};
priority_queue<P> q;
struct L{
    int to,next,length;
}bian[maxn];
void(int u,int v,int w){
    bian[++k].to=v;
    bian[k].length=w;
    bian[k].next=head[u];
    head[u]=k;
}
int dijkstra(){
    for(int i=0;i<+n;i++)dis[i]=inf;
    dis[s]=0;
    q.push((P){0,s});
    while(!q.empty()){
        int u=q.top().id;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=bian[i].next){
            int v=bian[i].to;
            if(dis[v]>dis[u]+bian[i].length){
                dis[v]=dis[u]+bian[i].length;
                q.push((P){dis[v],v});
            }
        }
	}
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>W;
        add(u,v,w);
	}
    dijkstra();
    cout<<dis[s][n];
    return 0;
}