Dijkstra算法笔记与思路整理

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Dijkstra算法笔记与思路整理，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1571字，纯文字阅读大概需要3分钟。

内容图文

该文章可能存在硬伤与不妥， 不能 作为教程阅读。

 

Dij作为单源最短路算法，需要先确定一个起点。Dij的函数主体为维护每个节点的dis和vis两个变量。dis表示该点距离起点的最短路权值和，vis存储该点是否被访问过。

设点数为n，无向边数为m，则要进行n次循环，每次循环中找出一个dis最小且vis不为真的点进行松弛操作。

这里抄一段百科：松弛操作是指对于每个顶点v∈V，都设置一个属性d[v]，用来描述从源点s到v的最短路径上权值的上界，称为最短路径估计(shortest-path estimate)。

然后就是优化：

　　(1)判断最小值的循环可用优先队列优化

　　(2)使用优先队列后可以直接判断堆中是否剩余元素来循环

　　(3)使用链表存储图，松弛操作只遍历相关的边

模板：

#include <bits/stdc++.h>
#define maxn 10010
#define maxm 10010
using namespace std;

struct edge{
    int to, val, next;
};
edge g[maxm];
int first[maxn], edge_cnt = 0;

struct node{
    int pos, dis;
};
priority_queue<node> q;
bool operator<(const node a, const node b){
    return a.dis > b.dis;
}
int dis[maxn], vis[maxn];

int n, m;
void in_put(){
    scanf("%d%d", &n, &m);    //n nodes, m edges
    for(int i=0; i<m; i++){
        int f, t, val;
        scanf("%d%d%d", &f, &val, &t);
        g[edge_cnt] = (edge){t, val, 0};
        g[edge_cnt].next = first[f];
        first[f] = edge_cnt;
        edge_cnt ++;
    }
}
void dijkstra(int start){
    vis[start] = 1;
    dis[start] = 0;
    q.push((node){start, dis[start]});
    while(q.size()){
        node curr = q.top();
        q.pop();
        int from = curr.pos;
        for(int i = first[from]; i ; i = g[i].next){
            if(dis[g[i].to] > g[i].val + curr.dis){
                dis[g[i].to] = g[i].val + curr.dis;
                q.push((node){g[i].to, dis[g[i].to]});
            }
        }
    }
    
}
int main(){
//    freopen(".in", "r", stdin);
//    freopen(".out", "w", stdout);
    memset(dis, 0x3f, sizeof(dis));
    in_put();
    dijkstra();
    return 0;
}

内容总结

以上是互联网集市为您收集整理的Dijkstra算法笔记与思路整理全部内容，希望文章能够帮你解决Dijkstra算法笔记与思路整理所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---