原理解释

Dijkstra算法是通过贪心+BFS+动态规划实现的，可以用来计算单个点（源点）到其余任一点的距离大小。

Dijkstra算法的实现分为以下几步：

  • 定义并初始化数组dis[N]，其中 disidis_{i} 表示源点当前距离 ii 点的最短距离，再定义一个 boolbool 数组 vis[N]， visivis_{i} 代表第 ii 个点是否被拓展过（即是否达到了最优解）。

  • 从未被拓展的点中找出一个离源点最近的点 xx（此时它已经是最优解），通过这个点依次松弛和它联通的每一个点距离源点的距离，同时将所松弛的点加入到队列当中。

  • 等到队列中没有元素存在之后，结束函数，此时 dis[N] 中的每个点 disidis_{i} 即代表着距离源点的最小距离。

代码实现

朴素法

1
2
3
struct Edge { int x, w; }; // x表示出点，w表示权值.
vector<Edge> g[N]; //存图数组
int dist[N]; //d[i]表示st距离i点的距离大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void dijkstra(int st)
{
    memset(dist, 0x3f, sizeof dist);
    dist[st] = 0;
    bitset<N> vis; // 初始化d数组全部变成无穷大，d[st]即表示与源点的距离为0

    for (int i = 1; i <= n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (t == -1 || (!vis[j] && dist[j] < dist[t]))
                t = j; // 找出离源点最近的一个点

        vis[t] = true; // 表示已经拓展过
        // 此时 d[u] 一定是最优的
        for (auto &y : g[t])
            if (!vis[y.x] && d[y.x] > d[t] + y.w)
                d[y.x] = d[t] + y.w;
    }
}

队列 / 堆优化

vector 存图

1
2
3
4
5
6
7
struct Edge
{
    int x, w; // x表示出点，w表示权值.
    bool operator < (const Edge &u) const { return w > u.w; }
};
vector<Edge> g[N];
int dist[N];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void dijkstra(int st)
{
    memset(dist, 0x3f, sizeof dist);
    dist[st] = 0;
    bitset<N> vis; // 初始化
    priority_queue<Edge> heap;
    heap.push({st, dist[st]}); // 将源点加入队列

    while (heap.size())
    {
        int t = heap.top().x;
        heap.pop();

        if (vis[t]) continue;
        vis[t] = true;

        for (auto &y : g[t])
        {
            if (!vis[y.x] && dist[y.x] > dist[t] + y.w) // 如果vis[y]则说明y点已经被拓展到最优解，无需更新
            {
                dist[y.x] = dist[t] + y.w; // y点目前仍然不是最优的，不可以进行拓展
                heap.push({y.x, dist[y.x]}); // 将y点加入队列中
            }
        }
    }
}

链式前向星

1
2
3
4
5
6
7
8
9
10
struct Edge
{
    int ver, val;
    bool operator < (const Edge &rhs) const { return val > rhs.val; }
};

int n, m, st;
int h[N], e[M], ne[M], w[M], idx;
int dist[N];
bool vis[N];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void dijkstra(int st)
{
    priority_queue<Edge> heap;
    memset(dist, 0x3f, sizeof dist), memset(vis, 0, sizeof vis);
    dist[st] = 0;
    heap.push({st, 0});
    
    while (!heap.empty())
    {
        auto [ver, val] = heap.top(); heap.pop();
        
        if (vis[ver]) continue;
        vis[ver] = true;
        
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int to = e[i];
            if (dist[to] > dist[ver] + w[i])
            {
                dist[to] = dist[ver] + w[i];
                heap.push({j, dist[j]});
            }
        }
    }
}