Dijkstra求最短路 II(堆优化Dijkstra算法)

2023-12-13 04:59:30

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

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

输入格式

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

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

输出格式

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

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

数据范围

1≤n,m≤1.5×10^5,
图中涉及边长均不小于?0,且不超过?10000。
数据保证:如果最短路存在,则最短路的长度不超过?10^9。

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

思路:这道题的堆优化我们使用优先队列来做(小根堆),而且因为我们既要存当前点到起点的距离,又要存当前点的编号,所以我们使用一个pair,又因为我们是根据距离来判断入堆的时机的(每次离起点最近的点入堆),所以优先排序的是距离,也就是pair的first元素应该是距离。

    typedef pair<int,int> PII;

    priority_queue<PII,vector<PII>,greater<PII>> heap; // 数据类型, 容器, 排序方式
    //定义一个升序的优先队列(小根堆)
    
    heap.push({0,1});  //放入距离,节点编号,这里1号点到1号点的距离是0 
   //这个顺序不能倒,pair排序时是先根据first,再根据second,这里显然要根据距离排序
    

先看完整代码?

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

using namespace std;
const int N=1e6+10;
typedef pair<int,int> PII;
int n,m;
int h[N],e[N],ne[N],w[N],idx; //稀疏图用邻接表存,w存边权值
int dist[N];  //1号点到n号点的最短距离
int st[N];  //当前点是否找到了最短距离

void add(int a,int b,int c) //添加一条从a指向b的边
{
    e[idx]=b;  //算法保证了会选出最短的路,所以不对重边或自环情况做处理,也就是会存在冗余
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx;
    idx++;
}

int dijkstra() //输出一个整数,表示1号点到n号点的最短距离。
{
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    
    priority_queue<PII,vector<PII>,greater<PII>> heap; // 数据类型, 容器, 排序方式
    //定义一个升序的优先队列(小根堆)
    
    heap.push({0,1});  //放入距离,节点编号,这里1号点到1号点的距离是0 
   //这个顺序不能倒,pair排序时是先根据first,再根据second,这里显然要根据距离排序
    
    while(heap.size())
    {
        auto t=heap.top(); //每次找到堆里面最小距离的点,也就是不在集合S中距离最短的点
        heap.pop();
        
        int ver=t.second,distance=t.first; //ver是节点编号,distance是点的距离
        
        if(st[ver]) continue; //如果ver这个点之前出来过,说明当前这个点是冗余(重边自环之类的),也就没有必要继续处理,直接continue,不再执行下面的语句,而是执行下一次的while循环
        
        /*
        堆优化版的是将距离直接加入到堆中.
        例如:dist[5]=9(在堆中{9,5},第一次更新时加入),dist[5]=7(在堆中{7,5},第二次更新时加入)
        使用时用的是dist[5]=7,将该点({7,5})弹出后,在下一次循环中,如果{9,5}在堆顶的话,使用时
        两者间肯定要选距离要小的那个,不能使用{9,5}重复更新,所以要用st数组进行标记
        */
        
        st[ver]=true; //如果这个点之前没有出来过,就标记找到了这个点的最短距离
        
        for(int i=h[ver];i!=-1;i=ne[i])  //每次都取这个距离最小的点来更新其他点,i是当前点ver指向的点的下标(与当前点与连线的点)
        {
            //更新ver指向的节点距离
            //每次只更新最小点的邻接边不是整个图
            
            int j=e[i];  //这里j是下标i对应的节点编号(i存的是下标,下标对应的点的值就是结点编号)
            if(dist[j]>dist[ver]+w[i])  //如果1到j的最短距离比1到ver的最短距离加上ver到j的距离大
            {
                dist[j]=dist[ver]+w[i]; //那么就更新1到j的最短距离,再把这个新的最短距离加入堆中
                heap.push({dist[j],j}); 
            }
        }
    }
    if(dist[n]==0x3f3f3f3f)
    {
        return -1;
    }
    return dist[n];
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    memset(h,-1,sizeof(h));
    cin>>n>>m;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dijkstra()<<endl;
    return 0;
}

//一个点到另一个点的距离有10,后来又加了15或者其他的更大距离,但是因为是小根堆,所以最短距离肯定会出现在最前面
//所以除了在堆顶的元素,底下那些元素都算是冗余备份元素,可以舍弃掉了,直接continue就行。

代码基本都比较好理解,注意这道题用邻接表存,其中e[ ]存的就是节点编号

 for(int i=h[ver];i!=-1;i=ne[i])  //每次都取这个距离最小的点来更新其他点,i是当前点ver指向的点的下标(与当前点与连线的点)
        {
            //更新ver指向的节点距离
            //每次只更新最小点的邻接边不是整个图
            
            int j=e[i];  //这里j是下标i对应的节点编号(i存的是下标,下标对应的点的值就是结点编号)
            if(dist[j]>dist[ver]+w[i])  //如果1到j的最短距离比1到ver的最短距离加上ver到j的距离大
            {
                dist[j]=dist[ver]+w[i]; //那么就更新1到j的最短距离,再把这个新的最短距离加入堆中
                heap.push({dist[j],j}); 
            }
        }
关于w[i]和i,j在这里面都代表什么:

 while(heap.size())
    {
        auto t=heap.top(); //每次找到堆里面最小距离的点,也就是不在集合S中距离最短的点
        heap.pop();
        
        int ver=t.second,distance=t.first; //ver是节点编号,distance是点的距离
        
        if(st[ver]) continue; //如果ver这个点之前出来过,说明当前这个点是冗余(重边自环之类的),也就没有必要继续处理,直接continue,不再执行下面的语句,而是执行下一次的while循环
        
        /*
        堆优化版的是将距离直接加入到堆中.
        例如:dist[5]=9(在堆中{9,5},第一次更新时加入),dist[5]=7(在堆中{7,5},第二次更新时加入)
        使用时用的是dist[5]=7,将该点({7,5})弹出后,在下一次循环中,如果{9,5}在堆顶的话,使用时
        两者间肯定要选距离要小的那个,不能使用{9,5}重复更新,所以要用st数组进行标记
        */
        
        st[ver]=true; //如果这个点之前没有出来过,就标记找到了这个点的最短距离
        
        for(int i=h[ver];i!=-1;i=ne[i])  //每次都取这个距离最小的点来更新其他点,i是当前点ver指向的点的下标(与当前点与连线的点)
        {
            //更新ver指向的节点距离
            //每次只更新最小点的邻接边不是整个图
            
            int j=e[i];  //这里j是下标i对应的节点编号(i存的是下标,下标对应的点的值就是结点编号)
            if(dist[j]>dist[ver]+w[i])  //如果1到j的最短距离比1到ver的最短距离加上ver到j的距离大
            {
                dist[j]=dist[ver]+w[i]; //那么就更新1到j的最短距离,再把这个新的最短距离加入堆中
                heap.push({dist[j],j}); 
            }
        }
    }
为什么要有continue和冗余?

代码中的for循环会把所有满足dist[j] > distance + w[i]的点都加进去,有的点它既是a的邻接点又是b的邻接点,这样的点可能会在将a的邻接点更新的时候加进去一次,又在更新b的邻接点的时候又加进去一次,这样队列中就有两个一样的点,虽然距离不同,此时这两个一样的点拓展的点也是一样的,所以我们取距离短的就好。

最后:

连线很多的时候,对应的就是稠密图,显然易见,稠密图的路径太多了,所以就用点来找,也就是抓重点;
点很多,但是连线不是很多的时候,对应的就是稀疏图,稀疏图的路径不多,所以按照连接路径找最短路,这个过程运用优先队列,能确保每一次查找保留到更新到队列里的都是最小的,同时还解决了两个点多条路选择最短路的问题;

参考:AcWing 850. Dijkstra求最短路 II - AcWing

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