首页 > 其他分享 >Dijkstra求最短路

Dijkstra求最短路

时间:2024-09-13 18:51:07浏览次数:11  
标签:dist int 短路 d% st Dijkstra include 号点

Dijkstra求最短路

849. Dijkstra求最短路 I

给定一个 n 个点 m条边的有向图,图中可能存在重边和自环,所有边权均为正值。
请你求出 1号点到 n号点的最短距离,如果无法从 1号点走到 n号点,则输出 −1。
输入格式
第一行包含整数 n和 m。

接下来 m行每行包含三个整数 x,y,z,表示存在一条从点 x到点 y的有向边,边长为 z。

输出格式
输出一个整数,表示 1号点到 n号点的最短距离。
如果路径不存在,则输出 −1。

数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。

输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3
解题思路:
本题目就是朴素版的dijkstra,其时间复杂度为n^2,适合的是所有边权为正的。
其思路为
S : 表示已经确定的最短距离的点
①dist[1]=0,dist[i]=inf
②for i : 1~n
t <- 不在S中的点
S <- t
用t更新其它点的最小距离,dist[x]>dist[t]+w;

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510;

int n,m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=1;i<=n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j])){
                t=j;
            }
        }
        for(int j=1;j<=n;j++){
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
        st[t]=true;
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof g);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
    }
    for(int i=1;i<=n;i++){//保证了不会走自环,其实在上面的步骤中st已经有这个作用了可以加,也可以不加
        for(int j=1;j<=n;j++)
          if(i==j){
              g[i][j]=0;
          }
    }
    printf("%d\n",dijkstra());
    return 0;
}

850. Dijkstra求最短路 II

给定一个 n个点 m条边的有向图,图中可能存在重边和自环,所有边权均为非负值。
请你求出 1号点到 n号点的最短距离,如果无法从 1号点走到 n号点,则输出 −1。

输入格式
第一行包含整数 n和 m。

接下来 m行每行包含三个整数 x,y,z,表示存在一条从点 x到点 y的有向边,边长为 z。

输出格式
输出一个整数,表示 1号点到 n号点的最短距离。
如果路径不存在,则输出 −1。

数据范围
1≤n,m≤1.5×105,
图中涉及边长均不小于 0,且不超过 10000。
数据保证:如果最短路存在,则最短路的长度不超过 109。
输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3
解题思路
本题目其实是对于dijkstra的堆优化版本,因为我们在朴素的版本中比遍历了所有的边,但其实多了很多与t不相关的点,那么我们优先队列存储t,访问其有关的边即可,时间复杂度为mlogn,适用于稀疏图,稠密图还是尽量用朴素版本的

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

#define x first
#define y second

using namespace std;

typedef pair<int,int> pii;

const int N = 1e6+10;

int n,m;
int h[N],e[N],w[N],ne[N],idx;
int dist[N];
bool st[N];

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    priority_queue<pii,vector<pii>,greater<pii>> heap;
    heap.push({0,1});
    while(heap.size()){
        auto t=heap.top();
        heap.pop();
        int ver = t.y, distance = t.x;
        if(st[ver]) continue;
        st[ver]=true;
        for(int i=h[ver];~i;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[ver]+w[i]){
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int t=dijkstra();
    printf("%d\n",t);
    return 0;
}

标签:dist,int,短路,d%,st,Dijkstra,include,号点
From: https://blog.csdn.net/weixin_46006714/article/details/142203479

相关文章

  • 【图论】Johnson全源最短路算法
    ·2024-9-11·最后更新时间2024-9-11作者学会了一个叫做\(Johnson\)的算法,所以就有了这篇博客......Johnson算法是一个高效处理全源最短路的算法其实也很慢,但目前是最高效的为了更加方便你们接下来的学习我希望你们已经掌握了基本的最短路算法(SPFA,Dijsktra,Bellman-Ford,Floyd......
  • dijkstra and spfa
    spfastructNode{ intw,to,nxt;}edg[maxn];inthead[maxn],tot;voidadd_edge(intu,intw,intv){ edg[++tot].nxt=head[u];edg[tot].to=v; edg[tot].w=w;head[u]=tot;}boolvis[maxn];intcnt[maxn],dis[maxn];boolspfa(intn,ints){ memset(dis,0x3f,sizeof......
  • 图与网络——最短路问题精解
    最短路问题(ShortestPathProblem)是图论中的一个经典问题,广泛应用于现实世界中的多个领域。该问题的核心在于如何在一个图中找到给定起点和终点之间路径权重最小的路径。路径权重通常代表时间、成本、距离等因素,因此最短路问题不仅具有理论上的研究价值,还在实际问题的解决中发挥了......
  • 【算法笔记】多源最短路问题——Floyd算法
    0.前言在图中,如果要求任意两点间的距离,则可以使用Floyd(\(\mathcalO(N^3)\)......
  • 【算法笔记】单源最短路问题——Dijkstra算法(无优化/优先队列/set优化)
    0.前言Dijkstra算法可在\(\mathcalO(m\logm)\)或\(\mathcalO(m\logn)\)的时间内求解无负权单源最短路问题。本文中,我们将详细介绍算法的原理、实现,以及常用的两种优化。另外,Dijkstra算法也不要乱用,比如说多源的最短路,用Dijkstra求解的复杂度只有\(\mathcalO(nm\logm)\),但......
  • MATLAB实现Dijkstra算法和Floyd算法
    目录1、文件功能介绍2、代码执行效果展示3、Dijkstra算法求图的单源最短路径4、DijkstrafullPath的更新逻辑5、DIjkstra算法流程图6、Floyd算法实现图的任意两点间最短路径7、Floyd算法流程图8、FloydfullPath的更新逻辑(非递归算法)1、文件功能介绍代码文件功能wor......
  • 信息学奥赛初赛天天练-86-NOIP2014普及组-基础题5-球盒问题、枚举算法、单源最短路、D
    1NOIP2014普及组基础题521把M个同样的球放到N个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的放置方法?(用K表示)()例如,M=7,N=3时,K=8;在这里认为(5,1,1)和(1,5,1)是同一种放置方法。问:M=8,N=5时,K=()22如图所示,图中每条边上的数字表示该边的长度,则从......
  • 信息学奥赛初赛天天练-86-NOIP2014普及组-基础题5-球盒问题、枚举算法、单源最短路、D
    信息学奥赛初赛天天练-86-NOIP2014普及组-基础题5-球盒问题、枚举算法、单源最短路、Dijkstra算法、Bellman-Ford算法PDF文档公众号回复关键字:202409081NOIP2014普及组基础题521把M个同样的球放到N个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的放置方法?(......
  • [USACO3.2] 香甜的黄油 Sweet Butter(Dijkstra)
     FarmerJohn发现了做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道NNN只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。FarmerJohn很狡猾。像以前的Pavlov,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特......
  • 最短路
    Bellman-Ford这是一种暴力求解单源最短路的方法。如果图不存在负环,那么任意两点之间的最短路一定不经过相同的点。假设\(A\)到\(E\)的最短路径为\(A\toB\toC\toD\toE\),那么\(A\toB\toC\toD\)一定为\(A\)到\(C\)的最短路。记\(dis_{x}\)表示起点\(s......