• 认为讲得好不妨支持一下

Dijkstra算法

• 是一种单源最短路算法
• 可以用堆优化
• 时间复杂度：优化前 $O(n^2)$ ，优化后 $O((m+n)logn)$

1 - 思路

所有的单源最短路算法的基本思路只有一个，

那就是： 拓展更新 ， $Dijkstra$ 便是其中的经典算法。

步骤

1. 预处理，除出发点到自身的最短距离为0以外，到其他点的最短距离都为无穷大；

2. 输入，加边，建图；

3. 找出图中所有 未用来更新过其它点 且 到出发点距离最小 的点 $P$ ；

4. 用点 $P$ 更新它 所有邻点 ，并标记点 $P$ 已被用过；

5. 重复上述3，4两步，只要是连通图，最多 $n-1$ 次就可以将点 $n$ 更新到。

原理

• 注：k是t的邻点，用t更新它所有的邻点。

使用堆优化来存一个二元组 {最短路长度, 点的编号} ，可以在步骤3处节省时间。

2 - 代码

例题： AcWing.849 Dijkstra求最短路

朴素算法

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 100010, INF = 0x3f3f3f3f;
int n, m;
int h[N], val[M], nxt[M], w[M], idx; //用来描述一个图
int dist[N]; //dist[i]表示第i个点的最短路长度
bool st[N]; //st[i]表示第i个点是否用于更新过它的邻点

//加边函数
void add(int a, int b, int c)
{
    val[idx] = b;
    w[idx] = c;
    nxt[idx] = h[a];
    h[a] = idx ++;
}

//Dijkstra主体
int Dijkstra()
{
    dist[1] = 0; //出发点到自身的距离为0
    for (int i = 0; i < n - 1; i ++)
    {
        int t = 0;
        //找出目前未使用过且最短路长度最小的点，
        for (int j = 1; j <= n; j ++)
            if (!st[j] && dist[j] < dist[t])
                t = j;
        //更新t的所有邻点
        for (int j = h[t]; j != -1; j = nxt[j])
        {
            int k = val[j];
            dist[k] = min(dist[k], dist[t] + w[j]);
        }
        //t被用过
        st[t] = true;
    }

    if (dist[n] == INF) return -1; //若n一次都没有被更新，说明不连通
    return dist[n];
}

//主函数
int main()
{
    memset(h, -1, sizeof(h));
    memset(dist, 0x3f, sizeof(dist)); //方便在第一次对点更新时用min函数

    scanf("%d%d", &n, &m);

    while (m --)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    printf("%d\n", Dijkstra());

    return 0;
}

堆优化

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII; // {最短路长度，点的编号}
const int N = 510, M = 100010, INF = 0x3f3f3f3f;
int n, m;
int h[N], val[M], nxt[M], w[M], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    val[idx] = b;
    w[idx] = c;
    nxt[idx] = h[a];
    h[a] = idx ++;
}

int Dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII> > q;
    //小根堆
    //若元素为pair型，根据pair中第一个量（最短路长度）排序

    dist[1] = 0;
    q.push({0, 1}); //放入编号为1的点（出发点），其最短路长度为0

    while (q.size())
    {
        auto u = q.top(); //取出目前最短路长度最小的点
        q.pop(); //u将被使用，无法继续留在q中
        int t = u.second;

        if (!st[t]) //若t被使用过了，直接跳过，不重复更新
        {
            st[t] = true;
            for (int i = h[t]; i != -1; i = nxt[i])
            {
                int k = val[i];
                if (dist[k] > dist[t] + w[i])
                {
                    dist[k] = dist[t] + w[i];
                    q.push({dist[k], k});
                }
            }
        }
    }

    if (dist[n] == INF) return -1;
    return dist[n];
}

int main()
{
    memset(h, -1, sizeof(h));
    memset(dist, 0x3f, sizeof(dist));

    scanf("%d%d", &n, &m);

    while (m --)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    printf("%d\n", Dijkstra());

    return 0;
}