韩鹏 发表于 2019-12-6 13:55:46

最短路径求解算法的实现和时间复杂度分析

大佬们，请帮帮忙，可额外支付宝转账，留言qq私聊

fury可 发表于 2019-12-7 12:08:21

根本看不懂   {:9_220:}

韩鹏 发表于 2019-12-7 20:05:40

fury可 发表于 2019-12-7 12:08
根本看不懂

太难了

月亮会发光 发表于 2020-1-11 23:14:46

本帖最后由 月亮会发光 于 2020-1-11 23:16 编辑

难

晴初back 发表于 2020-1-11 23:19:34

/*
由于本人没学Floyd就介绍 Dijkstra和SPFA
代码为c++

第一段代码用的是spfa算法，相对来说时间复杂度更高一些
如果图随机生成，时间复杂度为O(KM) (常数k想小一点小就看你自己怎么优化了)
但是实际上SPFA的算法复杂度是O(NM)。
不怎么推荐这个算法，比如2018年NOi比赛就卡了SPFA时间复杂度
（K可以当作常数，m边数，n点数）
*/
#include <iostream>
#include <cstdio>
#include <queue>
#define MAXN 10010
#define MAXM 500010
#define INF 2147483647
using namespace std;

queue<int> q;
struct Edge {
        int next,to,w;
}edge;
int n,m,s,cnt,head,vis,dis;

void spfa() {
        for(int i=1;i<=n;i++)
                dis = INF;
        q.push(s);
        dis = 0;
        vis = 1;
        while(!q.empty()) {
                int u = q.front();
                q.pop();
                vis = 0;
                for(int i=head;i;i=edge.next) {
                        int v = edge.to;
                        if(dis>dis+edge.w) {
                                dis = dis + edge.w;
                                if(!vis) {
                                        vis = 1;
                                        q.push(v);
                                }
                        }
                }
        }
}
void edge_add(int u,int v,int w) {
        cnt++;
        edge.next = head;
        edge.to = v;
        edge.w = w;
        head = cnt;
}

int main() {
        cin >> n >> m >> s;
        for (int i=1;i<=m;i++) {
                int u,v,w;
                cin >> u >> v >> w;
                edge_add(u,v,w);
        }
        spfa();
        for(int i=1;i<=n;i++)
                cout << dis << " ";
        return 0;
}





/*下面这段代码是Dijkstra
采用了优先队列priority_queue+重载的堆优化
priority_queue是c++ stl库里的东西，可以学习下

时间按复杂度O( (n+m) log n)
m很大的时候会比较慢
不过总的来说比SPFA优化了许多
*/
#include <iostream>
#include <cstdio>
#include <queue>
#define MAXN 100100
#define MAXM 5000100
#define INF 2147483647
using namespace std;


struct Edge {
        int next,to,w;
}edge;
int n,m,s,cnt,head,vis,dis;

struct node {
        int pos,dis;
        bool operator<(const node &a) const{
                return a.dis<dis;
        }
};
priority_queue<node> q;

void dj() {
        for(int i=1;i<=n;i++)
                dis = INF;
        dis = 0;
        node tmp;
        tmp.pos = s;
        tmp.dis = 0;
        q.push(tmp);
        while(!q.empty()) {
                int u = q.top().pos;
                q.pop();
                if(!vis) {
                        vis = 1;
                        for(int i=head;i;i=edge.next) {
                                int v = edge.to;
                                if(dis>dis+edge.w) {
                                        dis = dis + edge.w;
                                        tmp.pos = v;
                                        tmp.dis = dis;
                                        q.push(tmp);
                                }
                        }
                }
        }
}
void edge_add(int u,int v,int w) {
        cnt++;
        edge.next = head;
        edge.to = v;
        edge.w = w;
        head = cnt;
}

int main() {
        cin >> n >> m >> s;
        for (int i=1;i<=m;i++) {
                int u,v,w;
                cin >> u >> v >> w;
                edge_add(u,v,w);
        }
        dj();
        for(int i=1;i<=n;i++)
                cout << dis << " ";
        return 0;
}
页: [1]
查看完整版本: 最短路径求解算法的实现和时间复杂度分析