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

韩鹏

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

fury可

根本看不懂   

韩鹏

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

太难了

月亮会发光

难

晴初back

/*
由于本人没学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[MAXM];
int n,m,s,cnt,head[MAXN],vis[MAXN],dis[MAXN];

void spfa() {
        for(int i=1;i<=n;i++)
                dis[i] = INF;
        q.push(s);
        dis[s] = 0;
        vis[s] = 1;
        while(!q.empty()) {
                int u = q.front();
                q.pop();
                vis[u] = 0;
                for(int i=head[u];i;i=edge[i].next) {
                        int v = edge[i].to;
                        if(dis[v]>dis[u]+edge[i].w) {
                                dis[v] = dis[u] + edge[i].w;
                                if(!vis[v]) {
                                        vis[v] = 1;
                                        q.push(v);
                                }
                        }
                }
        }
}
void edge_add(int u,int v,int w) {
        cnt++;
        edge[cnt].next = head[u];
        edge[cnt].to = v;
        edge[cnt].w = w;
        head[u] = 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[i] << " ";
        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[MAXM];
int n,m,s,cnt,head[MAXN],vis[MAXN],dis[MAXN];

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[i] = INF;
        dis[s] = 0;
        node tmp;
        tmp.pos = s;
        tmp.dis = 0;
        q.push(tmp);
        while(!q.empty()) {
                int u = q.top().pos;
                q.pop();
                if(!vis[u]) {
                        vis[u] = 1;
                        for(int i=head[u];i;i=edge[i].next) {
                                int v = edge[i].to;
                                if(dis[v]>dis[u]+edge[i].w) {
                                        dis[v] = dis[u] + edge[i].w;
                                        tmp.pos = v;
                                        tmp.dis = dis[v];
                                        q.push(tmp);
                                }
                        }
                }
        }
}
void edge_add(int u,int v,int w) {
        cnt++;
        edge[cnt].next = head[u];
        edge[cnt].to = v;
        edge[cnt].w = w;
        head[u] = 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[i] << " ";
        return 0;
}