dijkstra堆优化

首先,我们概括一下大致思想(转载于Korpse——最短路径:Dijkstra算法)

注:Dijkstra算法适用于边权为正的无向和有向图,不适用于有负边权的图!(原因)

用途:
    用于求图中指定两点之间的最短路径,或者是指定一点到其它所有点之间的最短路径。实质上是贪心算法。

基本思想:
    1.将图上的初始点看作一个集合S,其它点看作另一个集合

    2.根据初始点,求出其它点到初始点的距离d[i] (若相邻,则d[i]为边权值;若不相邻,则d[i]为无限大)

    3.选取最小的d[i](记为d[x]),并将此d[i]边对应的点(记为x)加入集合S

    (实际上,加入集合的这个点的d[x]值就是它到初始点的最短距离)

    4.再根据x,更新跟 x 相邻点 y 的d[y]值:d[y] = min{ d[y], d[x] + 边权值w[x][y] },因为可能把距离调小,所以这个更新操作叫做松弛操作。

    (仔细想想,为啥只更新跟x相邻点的d[y],而不是更新所有跟集合 s 相邻点的 d 值? 因为第三步只更新并确定了x点到初始点的最短距离,集合内其它点是之前加入的,也经历过第 4 步,所以与 x 没有相邻的点的 d 值是已经更新过的了,不会受到影响)

    5.重复3,4两步,直到目标点也加入了集合,此时目标点所对应的d[i]即为最短路径长度。

    (注:重复第三步的时候,应该从所有的d[i]中寻找最小值,而不是只从与x点相邻的点中寻找。想想为什么?)

    图解:(动图很快,不容易理解,最好结合上面的步骤自己画一个图,一步一步消化)

    原理:这里不进行严格证明,Dijkstra的大致思想就是,根据初始点,挨个的把离初始点最近的点一个一个找到并加入集合,集合中所有的点的d[i]都是该点到初始点最短路径长度,由于后加入的点是根据集合S中的点为基础拓展的,所以也能找到最短路径。
原文链接:https://blog.csdn.net/kprogram/java/article/details/81225176

模板题:https://www.luogu.com.cn/problem/P4779

 下面对little_sun的题解进行解释

#include<bits/stdc++.h>//万能头不解释 

const int MaxN = 100010, MaxM = 500010;//表示不可改变数值的int常量。 

struct edge
{
    int to, dis, next;
    //to是此边的子节点
    //dis是此边的权值 
    //next是与此边父节点相同的最近的边(的编号)
    //即为上一条从此边的父节点引出的边(的编号) 
};

edge e[MaxM];
int head[MaxN], dis[MaxN], cnt;
//head数组指:以某点为父节点引出的最新一条边(的编号) 
bool vis[MaxN];
int n, m, s;

inline void add_edge( int u, int v, int d )
{
    cnt++;//新增一条边,编号要+1 
    e[cnt].dis = d;
    e[cnt].to = v;//这条边通向节点v,所以v是此边的一个子节点 
    e[cnt].next = head[u];
    //由于该边是新增的一条边,且父节点是u
    //那么上一条从u引出的边(的编号,即head[u])就是新增的这条边的next值 
    head[u] = cnt;
    //新增的这条边是从u引出的 ,那么这条边(的编号)自然是u的最新一条边 
}

struct node
{
    int dis;//距离 
    int pos;//表示从起点到达的点 
    bool operator <( const node &x )const
    {
        return x.dis < dis;
    }
    //重载运算符,对node类型的变量以dis为依据排序
    //这里重载的小于号 
};

std::priority_queue<node> q;
//定义优先队列(堆优化,类型是node类型) 

inline void dijkstra()
{
    dis[s] = 0;//s是起点 
    //定义从起点到点s的距离是0 
    q.push( ( node ){0, s} );
    //强制类型转换,定义node中的dis=0,pos=s
    //即定义,这一条边从起点到点s,距离是0 
    while( !q.empty() )//如果堆不空 
    {
        node tmp = q.top();//设置一个node型变量表示堆顶元素 
        q.pop();//因为已经用tmp存了,可以直接将堆顶元素删掉 
        int x = tmp.pos, d = tmp.dis;
        //x表示此边的来源(父节点),d表示距离(权值) 
        if( vis[x] )
            continue;
        //如果vis[x]被访问过,直接continue 
        vis[x] = 1;//如果没被访问过,标记为已访问 
        for( int i = head[x]; i; i = e[i].next )
        {
            //i从父节点为x的最新(后)一条边开始遍历
            //每次都等于与此边有相同父节点的上一条边,直到没有
            //e[i].next就是与正在进行遍历的这条边有相同的父节点的上一条边
            //例如节点5先后有1,2,3三条边,那么就从3开始,遍历3,2,1
            int y = e[i].to;
            //定义y是这条边通向的节点 
            if( dis[y] > dis[x] + e[i].dis )
            {
                //e[i].dis就是从节点x到节点y的各边的权值
                //因为在这个循环内我们定义的i就是从x引出的边 
                dis[y] = dis[x] + e[i].dis;
                //更新从起点到点y的最小值 
                if( !vis[y] )
                {
                    //如果节点y没被访问过 
                    q.push( ( node ){dis[y], y} );
                    //定义从起点到节点y的距离是dis[y] 
                }
            }
        }
    }
}

int main()
{
    scanf( "%d%d%d", &n, &m, &s );
    //给定一个n个点,m条有向边的带非负权图,请计算从s出发,到每个点的距离 
    for(int i = 1; i <= n; ++i)dis[i] = 0x7fffffff;
    //先把所有边的权值设为无穷大(在这里设为2147483647) 
    for( register int i = 0; i < m; ++i )
    {
        register int u, v, d;
        //表示从u到v有一条权值为d的有向边 
        scanf( "%d%d%d", &u, &v, &d );
        add_edge( u, v, d );
        //新增这条边,并存入e数组 
    }
    dijkstra();
    //调用函数寻找起点到每点的最小值 
    for( int i = 1; i <= n; i++ )
        printf( "%d ", dis[i] );
    //输出 
    return 0;
}

 

上一篇:最短路(dijkstra)


下一篇:最短路径之Dijkstra算法