Dijkstra

yyycj · 2025-07-28 21:57:54 · 算法·理论

Dijkstra 是一种基于贪心思想来求最短路的一种方式，但不支持负边权。

朴素版 Dijkstra 的时间复杂度为 O(N^{2})，它的主要思想为假设有两个序列，第一个序列存放的是已经求出最短路的点，第二个序列存放的则是未求出最短路的点。

所以想要求出所有点的最短路，就需要将所有点都添加进第一个序列。要求最短路，我们就应该每次将从第一个序列的所有点中能够最短到达第二个序列的某个点添加进第一个序列，不难发现，每次添加，都只需要从第一个序列中的点能够一步到达的点中选择点，因为没有负边权，所以需要两步到达的一定会比一步到达的长。

在这个过程中，将添加进第一个序列的点的最短路存储，就可以得到答案。

代码：

struct node {
    int p, w;  // p:点, w:边权
};

int dis[N];  // 最短路
bool vis[N];  // 是否处于第一个序列
vector<node> edge[N];

void dijsktra(int n, int s) {
    memset(dis, INT_INF, sizeof dis);
    dis[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++) {  // 找能够最短到达的第二个序列中的某个点
            if (vis[j]) continue;
            if (u == -1 || dis[j] < dis[u]) u = j;
        }
        vis[u] = true;
        for (node i : edge[u]) { // 更新距离
            dis[i.p] = min(dis[i.p], dis[u] + i.w);
        }
    }
}

但是我们发现找能够最短到达的第二个序列中的某个点这个操作的时间复杂度是 O(N) 的，在部分情况下会超时，所以就有了时间复杂度 O(M \log N) 的堆优化版本。

堆优化就是创建一个小根堆，我们在更新距离的时候，就将距离与点一起存入小根堆，根据距离来确定顺序，这样就不需要用 O(N) 去求，每次的堆顶就是最短能够到达的。

代码：

struct node {
    int p, w;
};

int dis[N];
bool vis[N];
vector<node> vec[N];

void dijsktra(int s) {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
    q.push(make_pair(0, s));
    memset(dis, INT_INF, sizeof dis);
    dis[s] = 0;
    while (!q.empty()) {
        pair<int, int> u = q.top(); q.pop();
        if (vis[u.second]) continue;  // 判断是否已经在第一个序列
        vis[u.second] = true;
        for (node i : vec[u.second]) {
            if (dis[i.p] > dis[u.second] + i.w) {
                dis[i.p] = dis[u.second] + i.w;
                q.push(make_pair(dis[i.p], i.p));
            }
        }
    }
}

但是第一个版本的时间复杂度与点数有关，但与边数无关；第二个版本的时间复杂度大多与边数有关。所以当这个图为稠密图时，用 O(N^{2}) 的版本可能会优于 O(M \log N) 的版本。