Dijkstra算法+邻接表用堆优化的原理

senuo · 2023-09-12 19:57:12 · 个人记录

Dijkstra算法的目标是找到从源点到所有其他点的最短路径。

基础版本的Dijkstra算法会使用两层循环：外层循环遍历所有点，内层循环找到当前未访问的、距离最短的点。这种实现的时间复杂度是O(n 2 )。

使用邻接表+堆进行优化的Dijkstra算法则是为了减少寻找当前未访问的、距离最短的点的时间。具体来说：

• 邻接表：通过存储每个节点的邻居，我们可以快速找到与给定节点直接相连的所有节点。这比邻接矩阵更加高效，因为邻接表只存储非零条目，尤其是在稀疏图中。
• 优先队列（堆）：优先队列（通常实现为二叉堆）允许我们在对数时间内找到和删除当前未访问的、距离最短的点。每次从优先队列中取出距离最短的点，并更新它的邻居的距离，然后将这些邻居放入优先队列中。

结合这两种优化，Dijkstra算法的时间复杂度可以降低到 O ( m log ⁡ n ) O(mlogn)，其中 m m是边的数量， n n是节点的数量。

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e4 + 5; // 最大的节点数量
const int MAX_M = 5e5 + 5; // 最大的边数量

struct Edge
{
    int to, weight, next;
} edges[MAX_M];

int head[MAX_N], dist[MAX_N];
int edge_count = 0;

void add_edge(int u, int v, int w)
{
    edges[edge_count].to = v;
    edges[edge_count].weight = w;
    edges[edge_count].next = head[u];
    head[u] = edge_count++;
}

void dijkstra(int start)
{
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

    dist[start] = 0;
    pq.push(make_pair(0, start));

    while (!pq.empty())
    {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        if (d > dist[u])
            continue;

        for (int i = head[u]; i != -1; i = edges[i].next)
        {
            int v = edges[i].to;
            int w = edges[i].weight;
            if (dist[u] + w < dist[v])
            {
                dist[v] = dist[u] + w;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
}

int main()
{
    int n, m, s;
    cin >> n >> m >> s;

    memset(head, -1, sizeof(head));
    fill(dist, dist + n + 1, INT_MAX);

    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
    }

    dijkstra(s);

    for (int i = 1; i <= n; i++)
    {
        cout << (dist[i] == INT_MAX ? -1 : dist[i]) << " ";
    }

    return 0;
}