迪杰斯特拉算法的优化

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了迪杰斯特拉算法的优化，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1733字，纯文字阅读大概需要3分钟。

内容图文

在学习迪杰斯特拉算法之后，听说它可以被优化，但一直没有学习。

---

因为听到线段树，斐波那契堆就怕。

后面发现优先队列也可以实现优化，不过关于重载运算符那时候却没怎么懂现在终于会了。

我们在使用迪杰斯特拉算法的时候每次都要使用起点位置最短的点，如果每次都遍历的化时间复杂度会到达n^2。

于是我们就可以创建一个结构体记录它当前位置以及到达起点的距离，通过优先队列每次都取到达起点距离最小的点入队，时间复杂度便成了nlogn。

不说了粘代码。

#include<iostream>
#include<queue>
const int INF=0x7fffffff;
using namespace std;
int head[200005], now = 1, dis[100005],vis[100005];
bool book[100008];
struct edg {
    int nex, to, l;
}edge[200005];
void add_edge(int at, int to, int l) {
    edge[now].nex = head[at];
    edge[now].l = l;
    edge[now].to = to;
    head[at] = now++;
}
struct node {
    int at, dis;
     node(int a, int b) {
         at = a; dis = b;
    }
     bool operator <(const node& x)const//这里的引用&可有可无，不过为了规范最好加上
     {
         return x.dis < dis;
     }
};
int main() {
    int n, m, s; cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int a, b, c; cin >> a >> b >> c;
        add_edge(a, b, c);
    }
    for (int i = 1; i <= n; i++) dis[i] = INF;
    dis[s] = 0;
    node now(s, 0);
    priority_queue <node> q;
    q.push(now);
    while (!q.empty()) {
        now = q.top(); q.pop();
        if (vis[now.at])
            continue;
        vis[now.at] = 1;
        for (int i = head[now.at]; i; i = edge[i].nex) {
            int x = edge[i].to;
            if (dis[x] > dis[now.at] + edge[i].l) {
                dis[x] = dis[now.at] + edge[i].l;
                if (!vis[x]) {
                    node o(edge[i].to, dis[x]);
                    q.push(o);
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << dis[i]<<" ";
    return 0;
}

那么为了使用优先队列，我们在结构体中加了个重载运算符的操作。

c++允许对运算符进行重载，比如为了使结构体相加，我们不需要写一个函数，只要重新为+号做一个定义就可以了。

而operator就是运算符重载的关键字。

这里我们进行了<号的重载，使得优先队列知道应该将dis较小的node放在前面。

内容总结

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

内容备注

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

内容手机端

---