Noob Dream

 找回密码
 加入我们[Register]
搜索
查看: 138|回复: 0

最短路算法(Dijkstra以及优化)

[复制链接]

21

主题

21

帖子

112

积分

超级版主

Rank: 8Rank: 8

积分
112
发表于 2018-5-6 13:49:14 | 显示全部楼层 |阅读模式
本帖最后由 Gzu_lx 于 2018-5-10 21:10 编辑

Dijkstra模板
复杂度O(V^2 + E)
代码:
[C++] 纯文本查看 复制代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define INF 0x3f3f3f3f
const int maxn = 105;
int mpt[maxn][maxn];
int n, m;
int dist[maxn];
int vis[maxn];

void dijkstra() {
    dist[1] = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; i++) {
        int min_p = -1;
        int min_len = INF;
        for (int j = 1; j <= n; j++) {
            if (min_len > dist[j] && vis[j] == 0) {
                min_len = dist[j];
                min_p = j;
            }
        }
        //printf("%d\n", min_p);
        vis[min_p] = 1;
        if (min_p == -1) break;
        for (int j = 1; j <= n; j++) {
            if (dist[j] > dist[min_p] + mpt[min_p][j] && vis[j] == 0)
                dist[j] = dist[min_p] + mpt[min_p][j];
        }
    }
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        if (n + m == 0) break;
        for (int i = 1; i <= n; i++) {
            dist[i] = INF;
            for (int j = 1; j <= n; j++) {
                if (i == j) mpt[i][j] = 0;
                else mpt[i][j] = INF;
            }
        }
        for (int i = 1; i <= m; i++) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            if (c < mpt[a][b]) {
                mpt[a][b] = c;
                mpt[b][a] = c;
            }
        }
        dijkstra();
        printf("%d\n",dist[n]);
    }
    return 0;
}


用优先队列优化+邻接表优化
复杂度O((V + E)log(V)))
代码:

[C++] 纯文本查看 复制代码
/*
dijkstra + heap
*/
#include <stdio.h>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;

#define INF 0x3f3f3f3f
const int maxn = 105;
int n, m;

struct Edge{
    int u, v, w;
    Edge(int u, int v, int w):u(u),v(v),w(w) {}
};

struct node {
    int d, u;
    node(int d, int u):d(d),u(u) {}
    friend bool operator < (node a, node b) {
        return a.d > b.d;
    }
};

vector<Edge> edges;
vector<int> G[maxn];
int dist[maxn]; // 存放起点到i点的最短距离
int vis[maxn]; // 标记是否访问过
int p[maxn]; // 存放路径

void dijkstra(int s) {
    priority_queue<node> q;
    for (int i = 0; i <= n; i++) dist[i] = INF;
    dist[s] = 0;
    memset(vis, 0, sizeof(vis));
    q.push(node(0, s));
    int cnt = 0; //统计松弛次数
    while (!q.empty()) {
        node now = q.top(); q.pop();
        int u = now.u;
        if (vis[u]) continue;
        vis[u] = 1;
        cnt++;
        if(cnt >= n) break; // 小优化
        for (int i = 0; i < G[u].size(); i++) { // // Sum -> O(E)
            Edge& e = edges[G[u][i]];
            if (dist[e.v] > dist[u] + e.w) { // O(lgV)
                dist[e.v] = dist[u] + e.w;
                p[e.v] = G[u][i];
                q.push(node(dist[e.v], e.v));
            }
        }
    }
}

void addedge(int u, int v, int w) {
    edges.push_back(Edge(u, v, w));
    int sz = edges.size();
    G[u].push_back(sz - 1);
}

void init() {
    for(int i = 0; i <= n; i++) G[i].clear();
    edges.clear();
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        if (n + m == 0) break;
        init();
        for (int i = 0; i < m; i++) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            addedge(a, b, c);
            addedge(b, a, c);
        }
        dijkstra(1);
        printf("%d\n",dist[n]);
    }
    return 0;
}


回复

使用道具 举报

本版积分规则

QQ|Noob Dream

GMT+8, 2018-8-15 12:53 , Processed in 0.119912 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表