Dijkstra求最短路 I(Dijkstra算法)

2023-12-14 20:14:59

给定一个?n?个点?m 条边的有向图,图中可能存在重边和自环,所有边权均为正值。

请你求出?1?号点到?n?号点的最短距离,如果无法从?1?号点走到?n?号点,则输出??1。

输入格式

第一行包含整数?n?和?m。

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

输出格式

输出一个整数,表示?1?号点到?n?号点的最短距离。

如果路径不存在,则输出 ?1。

数据范围

1≤n≤500,
1≤m≤10^5,
图中涉及边长均不超过10000。

输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3

思路:

最短路问题,可以用dijkstra算法来解决,这里是解决各种最短路问题的框架

因为这道题求的是单源最短路,且每条路权值都为正数,并且边的量级明显大于点(1≤n≤500,
1≤m≤10^5),是稠密图,所以用朴素dijkstra算法解决

朴素dijkstra算法的原理:

初始化,除了起点之外,每个点到起点的距离为无穷大。我们创建一个集合s,表示当前已确定最短距离的点,对于n个点,循环n次,每次找到一个不在集合s中的离起点(题目中的1号点)最近的点,然后将它加入集合s,并用这个点去更新其他所有点距离。

const int N=510;
int n,m;
int g[N][N];  //题目中是稠密图,用邻接矩阵写,g[1][2]表示从1节点指向2节点的距离
int dist[N];  //从1号点走到每个点的距离(最短距离)
bool st[N];  //每个点最短路是否已经确定,true为确定

因为是稠密图,所以我们用邻接矩阵g[ ][ ]存储边和点的关系。

   for(int i=0;i<n;i++) //迭代n次,每次做两件事:1.找到集合外到起点最短距离的点 2.用这个点来更新到其他点的最短距离
    {
        int t=0;  //t表示当前要找的集合外到起点最短距离的点,0表示初始化

        for(int j=1;j<=n;j++) //第一轮循环,寻找集合外到起点最短距离的点,一开始1号点也是在集合外的,所以j从1开始找
        {
            //找当前不确定最短距离的点集合外(即st为false)到起点距离最短的点
            if(!st[j] && (dist[t]>dist[j])) //当前点最短路还没被确定并且当前t不是最短的,一开始的d[t]是无穷,d[1]是0,所以1号点就会找到
            {
                t=j; //换成短的那条路 
            }
        }
        st[t]=true;  //找到了集合外到起点最短距离的点,标记(其实就是加入了确定最短距离的集合)
        for(int j=1;j<=n;j++) //第二轮循环,用已经确定了的最短距离的点来更新到其他点的最短距离
        {
            dist[j]=min(dist[j],dist[t]+g[t][j]); //更新1到j这条路的长度(从1到t,再从t到j的距离与1到j距离比较,换成短的那条路)
        }      
    }

dijkst算法的核心代码,进行n次循环,每次循环找到集合外到起点最短距离的点 ,然后用这个点来更新到其他点的最短距离。

        for(int j=1;j<=n;j++) //第一轮循环,寻找集合外到起点最短距离的点,一开始1号点也是在集合外的,所以j从1开始找
        {
            //找当前不确定最短距离的点集合外(即st为false)到起点距离最短的点
            if(!st[j] && (dist[t]>dist[j])) //当前点最短路还没被确定并且当前t不是最短的,一开始的d[t]是无穷,d[1]是0,所以1号点就会找到
            {
                t=j; //换成短的那条路 
            }
        }
        st[t]=true;  //找到了集合外到起点最短距离的点,标记(其实就是加入了确定最短距离的集合)

经过第一次循环后,我们找到了一个点t,将它加入集合s,这里每次t初始化为0,dist[0]=0x3f3f3f3f,保证了后面(dist[t]>dist[j])找到的是集合s外的点的离起点最近的点,因为dist[t]是最大的(正无穷),多次比较之后,dist值最小的点就会加入集合s。

        for(int j=1;j<=n;j++) //第二轮循环,用已经确定了的最短距离的点来更新到其他点的最短距离
        {
            dist[j]=min(dist[j],dist[t]+g[t][j]); //更新1到j这条路的长度(从1到t,再从t到j的距离与1到j距离比较,换成短的那条路)
        }    

第二个循环:用当前找到的点t去更新后面的点到起点的距离,方法就是遍历1到n,每次看是1号点到j号点的距离大还是1号点到t号点,再从t号点到j号点的距离大,我们保留短的那条路。

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c); //如果两个点之间有多条边,保留最短边,因为初始化g为无穷大,所以一开始是让g[a][b]=c,后面如果出现了一样的点,就会取其中的最小值
    }

在主函数中,因为题目没有说不存在自边和环,所以可能从一个点到另一个点有多条边,我们只需要保留其中最短的就好。

补充:这里的代码很多处都用到了0x3f,是因为这个数字能近似表达正无穷,它的值是1061109567,是10^9级别,并且还能保证无穷大加无穷大仍然不会超限,因为0x3f3f3f3f+0x3f3f3f3f=2122219134,这非常大但却没有超过32-bit int的表示范围,我们使用memset()是对char操作,即一个字节一个字节的操作,如果此时初始化的变量为int类型(4字节),那么此时的变量就会被初始化成四个0x3f,即0x3f3f3f3f(这个0x是十六进制的意思)。

  if(dist[n] == 0x3f3f3f3f)  //当1号点距离到n号点距离为无穷大时(即1和n不连通),注意这里变成了0x3f3f3f3f
    {
        return -1;
    }

在后面比较的时候,注意这个值是0x3f3f3f3f,我们只是用memset赋值的时候给每个字节赋值0x3f,整个int变量是0x3f3f3f3f。?

参考:0x3f~0x3f3f3f3f的来龙去脉(详解)-CSDN博客关于memset函数和赋值0x3f,2021-5-5-CSDN博客

示例代码:
#include<iostream>
#include<cstring>
#include<algorithm> 

using namespace std;
const int N=510;
int n,m;
int g[N][N];  //题目中是稠密图,用邻接矩阵写,g[1][2]表示从1节点指向2节点的距离
int dist[N];  //从1号点走到每个点的距离(最短距离)
bool st[N];  //每个点最短路是否已经确定,true为确定

int dijkstra() 
{
    memset(dist,0x3f,sizeof(dist)); //初始化时每个点到起点距离为无穷大
    dist[1]=0;  //起点到自身的距离为0
    for(int i=0;i<n;i++) //迭代n次,每次做两件事:1.找到集合外到起点最短距离的点 2.用这个点来更新到其他点的最短距离
    {
        int t=0;  //t表示当前要找的集合外到起点最短距离的点,0表示初始化

        for(int j=1;j<=n;j++) //第一轮循环,寻找集合外到起点最短距离的点,一开始1号点也是在集合外的,所以j从1开始找
        {
            //找当前不确定最短距离的点集合外(即st为false)到起点距离最短的点
            if(!st[j] && (dist[t]>dist[j])) //当前点最短路还没被确定并且当前t不是最短的,一开始的d[t]是无穷,d[1]是0,所以1号点就会找到
            {
                t=j; //换成短的那条路 
            }
        }
        st[t]=true;  //找到了集合外到起点最短距离的点,标记(其实就是加入了确定最短距离的集合)
        for(int j=1;j<=n;j++) //第二轮循环,用已经确定了的最短距离的点来更新到其他点的最短距离
        {
            dist[j]=min(dist[j],dist[t]+g[t][j]); //更新1到j这条路的长度(从1到t,再从t到j的距离与1到j距离比较,换成短的那条路)
        }      
    }
    
    if(dist[n] == 0x3f3f3f3f)  //当1号点距离到n号点距离为无穷大时(即1和n不连通),注意这里变成了0x3f3f3f3f
    {
        return -1;
    }
    return dist[n];   //返回从1号点走到n号点的距离(最短距离)
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;  //读入点数和边数
    memset(g,0x3f,sizeof(g));  //0x3f是无穷大,memset按字节赋值,一个字节就是0x3f,int有四个字节,所以是0x3f3f3f3f
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b]=min(g[a][b],c); //如果两个点之间有多条边,保留最短边,因为初始化g为无穷大,所以一开始是让g[a][b]=c,后面如果出现了一样的点,就会取其中的最小值
    }
    cout<<dijkstra();
    return 0;
}

文章来源:https://blog.csdn.net/weixin_63504072/article/details/134932470
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。