Skip to content

最短路#

目录#

1. 模板#

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int INF = 1e5 + 1;
const int NUM = 1e5 + 1;

int list[NUM];

struct edge {
    int from, to, w;
    // 边：起点，终点，权值。起点from并没有用到，e[i]的i就是from
    edge(int a, int b, int c)
    {
        from = a;
        to = b;
        w = c;
    }
};

// 用于存储图
vector<edge> e[NUM];

struct s_node {
    // id：结点；n_dis：这个结点到起点的距离
    int id, _dis;
    s_node(int b, int c)
    {
        id = b;
        n_dis = c;
    }
    bool operator<(const s_node& a) const { return n_dis > a.n_dis; }
};

int n, m;
// 记录前驱结点
int pre[NUM];

// 打印从s到t的最短路径
void print_path(int s, int t)
{
    if (s == t) {
        printf("%d", s);
        return;
    }
    print_path(s, pre[t]);
    printf("%d", t);
}

// 找出从start到end的最短路径距离
void dijkstra(int start, int end)
{
    // 起点s
    int s = start;
    // 记录所有结点到起点的距离
    int dis[NUM];
    // 记录已访问过的结点
    bool done[NUM];
    // 初始化
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
        done[i] = false;
    }
    // 起点到自己的距离是0
    dis[s] = 0;
    // 优先队列，存结点信息
    priority_queue<s_node> Q;
    // 起点进队列
    Q.push(s_node(s, dis[s]));
    while (!Q.empty()) {
        // pop出距起点s距离最小的结点u
        s_node u = Q.top();
        Q.pop();
        // 丢弃已找到的最短路径的结点，即集合A中的结点
        if (done[u.id]) {
            continue;
        }
        done[u.id] = true;
        // 检查结点u的所有邻居
        for (size_t i = 0; i < e[u.id].size(); i++) {
            // u.id 的第i个邻居是y.to
            edge y = e[u.id][i];
            if (done[y.to]) {
                // 丢弃已经找到最短路径的邻居结点
                continue;
            }
            // *如果找到更大的路径
            if (dis[y.to] > y.w + u.n_dis) {
                dis[y.to] = y.w + u.n_dis;
                // 扩展新的邻居，放到优先队列中
                Q.push(s_node(y.to, dis[y.to]));
                // 记录路径
                pre[y.to] = u.id;
            }
        }
    }
    printf(" %d\n", dis[end]);
    // 打印路径
    // print_path(s, n);
}
Back to top