【图论】Dijkstra

这篇文章介绍了【图论】Dijkstra，分享给大家做个参考，收藏Python资料网收获更多编程知识

Dijkstra

---

前置知识

• 堆
• 图论基础
• Bellman-Ford

---

思路

Dijkstra 算法是一种求正权图单源最短路的算法。

注意到BF最大的缺陷在于其对于一个点的松弛方式太暴力了。
注意到有正权这个条件。
那么我们发现，只要选取当前距离最小的点，该点不可能被松弛。
于是使用一个小根堆维护距离即可。

---

算法参数

• 时间复杂度：$O(m\log n)$
• 空间复杂度：$O(n+m)$

---

实现代码

struct node{int u,d;};
bool operator<(node a,node b){return a.d>b.d;}
void Dijkstra(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    priority_queue<node> q;
    q.push({s,0});
    while (!Q.empty()){
        node cur=q.top();
        q.pop();
        int u=fr.u,k=fr.d;
        if (k!=d[u]) continue;
        for (node e:G[u]){
            int v=e.v,w=e.w;
            if (d[u]+w<d[v]){
                d[v]=d[u]+w;
                q.push({v,d[v]});
            }
        }
    }
}

---

练习

• P3371
• P4779
• P1339

版权声明：本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！