一、题意

输入一个n个点m条边的无向图，每条边给出边权，求从点1到点n的最短路径。

二、解析

最短路径模板题。用来复习一下Dijkstra算法的模板正好。
Dijkstra算法的时间复杂度为O(mlgn)，一般对于边权为正的单源最短路问题就它就没错了。同时适用于有向图和无向图。

三、代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 1000 + 5, INF = 1 << 30;
struct node {
    int u, d;
    node(int u, int d) : u(u), d(d) {}
    bool operator < (const node& rhs) const {
        return d > rhs.d;  // 由于默认为最大堆, 而我们希望最小的先出列
    }
};
struct edge {
    int to, w;
    edge(int to, int w) : to(to), w(w) {}
};
vector<edge> G[maxn];
int n, m, vis[maxn], d[maxn];

void Dij(int s) {
    fill(d, d + n + 1, INF), d[s] = 0;  // 初始化d数组
    fill(vis, vis + n + 1, 0);
    priority_queue<node> que;
    que.push(node(s, 0));
    while(!que.empty()) {
        int u = que.top().u;
        que.pop();
        if(vis[u]) continue;  // vis判定
        vis[u] = 1;
        for(int i = 0; i < G[u].size(); i ++) {
            const edge& e = G[u][i];
            if(d[e.to] > d[u] + e.w) {  // 松弛操作
                d[e.to] = d[u] + e.w;
                que.push(node(e.to, d[e.to]));
            }
        }
    }
}

int main() {
    cin >> m >> n;
    while(m --) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(edge(v, w));
        G[v].push_back(edge(u, w));
    }
    Dij(1);
    cout << d[n] << endl;
}

四、归纳

  • Dijkstra算法用于求边权为正的单源最短路问题，模板如下： 
struct node {  // node结构是存放在优先队列中的结构
    int u, d;
    node(int u, int d) : u(u), d(d) {}
    bool operator < (const node& rhs) const {
        return d > rhs.d;  // 由于默认为最大堆, 而我们希望最小的先出列
    }
};
struct edge {  //edge结构仅用于存图
    int to, w;
    edge(int to, int w) : to(to), w(w) {}
};
vector<edge> G[maxn];
int n, m, vis[maxn], d[maxn];

void Dij(int s) {
    fill(d, d + n + 1, INF), d[s] = 0;  // 初始化d数组
    fill(vis, vis + n + 1, 0);
    priority_queue<node> que;
    que.push(node(s, 0));
    while(!que.empty()) {
        int u = que.top().u;
        que.pop();
        if(vis[u]) continue;  // vis就写在这两行，是为了忽略掉松弛前的结点（因为并没有从队列中删除，只是压入了d更小的状态而已），
        vis[u] = 1;           // 因此放在这里进行判断，这是和bfs不同的
        for(const edge& e : G[u]) {
            if(d[e.to] > d[u] + e.w) {  // 松弛操作
                d[e.to] = d[u] + e.w;
                que.push(node(e.to, d[e.to]));  // 压入了松弛后的结点，然而并没有删除原结点，因此要依靠上面的vis
            }
        }
    }
}

int main() {
    ......
    Dij(1);
    ......
}

注意Dijkstra的模板和bfs有点像，但是还是不一样的：

  • 一个用优先队列，一个用普通队列
  • 使用vis数组的原因不同