首页 > 其他分享 >Dijkstra

Dijkstra

时间:2022-10-23 13:44:17浏览次数:65  
标签:head int length bian Dijkstra maxn dis

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;
}

标签:head,int,length,bian,Dijkstra,maxn,dis
From: https://www.cnblogs.com/alwayslove/p/16818436.html

相关文章

  • dijkstra 求最小环( CCPC桂林 - E. Buy and Delete )
    原文题意经过转化后,本质就是求最小环。有向图有以下三种实现方式,而无向图只能用第一种实现方式。实现方式1:删边求最短距离有向图实现方式2:回到起点构成环有向图实现......
  • 算法 -Dijkstra算法
    以这个图为例,找到从起点到终点的耗时最短的路径(圆圈连线上的数字代表耗时)。graph={}graph["start"]={}graph["start"]["a"]=6graph["start"]["b"]=2graph["a"]={}graph["a......
  • ac 849 dijkstra
    时间复杂度为n^2#include<bits/stdc++.h>usingnamespacestd;constintN=510;intn,m;intdist[N];//每个点到起点的最短距离boolst[N];//判断某个点......
  • SPAFA 和Dijkstra的区别
    Dijkstra算法和SPFA算法都可以用于求单源最短路,前者可以用小根堆进行优化,后者用就是用队列优化过的Bell-manFord,下面说一说这两者的区别:Dijkstra算法是基于贪心和DP的思......
  • 最短路径问题---Dijkstra算法详解
    0.最短路径问题介绍问题解释:从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径1.Dijkstra算法介绍算法特点:迪科斯彻算法使用......
  • Dijkstra算法
    求是单源最短路径,即给定一个源点,求其到其他顶点的最短路径。Dijkstra算法就是解决它的,而其前提条件是图中每条边的权重不为负值。朴素版用于处理稠密图,使用邻接矩阵存储......
  • SPAFA 和Dijkstra的区别
    SPAFA和Dijkstra的区别Dijkstra算法和SPFA算法都可以用于求单源最短路,前者可以用小根堆进行优化,后者用就是用队列优化过的Bell-manFord,下面说一说这两者的区别:Dijkstra......
  • 堆优化dijkstra的两种写法
    例题:https://www.acwing.com/problem/content/description/1131/1、仅用dis数组记录,出队时记录最小距离#include<bits/stdc++.h>#definefore(x,y,z)for(LLx=(y);......
  • 最短路算法之 Dijkstra
    部分内容参考了李煜东的《算法竞赛进阶指南》,在此声明。单源最短路径单源最短路径问题,是说,给定一张有向图(无向图)\(G=(V,E)\),\(V\)是点集,\(E\)是边集,\(|V|=n\),\(|......
  • 最短路径算法-迪杰斯特拉(Dijkstra)算法在c#中的实现和生产应用
    迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先遍历思想),直到扩展到终点为止......