算法过程

假设我们用数据结构 $f$ 维护每个点的 $dis$

  1. 初始化 $dis_S=0$ 并加入 $f$, 其余点的 $dis$ 设为无限大, 所有点标记为未访问
  2. 重复3-5，直到没有未访问的点，算法结束
  3. 从 $f$ 中选出 $dis$ 最小且未访问的点，记为 $u$（$f$中查询）
  4. 把 $u$ 标记为已访问并把它从 $f$ 中删除（$f$中删除）
  5. 对 $u$ 所有出边进行松弛操作（$f$中修改和插入）

适用范围

单源多汇最短路，无负权边

解释

已经访问的点是已经确定了最短路的点，未访问的点是有待确认的点

对于一个未访问的点中 $dis$ 最小的点，它的 $dis$ 首先已经被已经访问过的点松弛过了，所以能让它 $dis$ 更小的未访问的点不存在

而其他的点的 $dis$ 都不比它小，且边权非负，也不能让 $dis$ 更小，所以这个点的最短路确定就是 $dis$ 了

对不同$f$的复杂度分析

暴力

操作3的总复杂度为 $ n*\mathcal{O}(n)=\mathcal{O}(n^2) $

操作5的总复杂度为 $ \mathcal{O}(m) $

复杂度 $ \mathcal{O}(n^2+m) = \mathcal{O}(n^2) $

堆

操作3总复杂度为 $ \mathcal{O}(n) $

操作4总复杂度为 $ \mathcal{O}(n\log{}n) $

操作5总复杂度为 $ \mathcal{O}(m\log{}n) $

复杂度 $ \mathcal{O}(n+(n+m)\log{}n) = \mathcal{O}(m\log{}n) $

优先队列

类似于堆，但是没有修改和删除操作，所以队内元素有 $\mathcal{O}(m)$ 个

操作3总复杂度为 $ \mathcal{O}(m) $

操作5总复杂度为 $ \mathcal{O}(m\log{}m) $

复杂度 $ \mathcal{O}(m+m\log{}m) = \mathcal{O}(m\log{}m) $

不过 $ \mathcal{O}(\log{}m)=\mathcal{O}(\log{}n) $，因为 $m$ 最多是 $\mathcal{O}(n^2)$ 的

结论

稀疏图中，$ m=\mathcal{O}(n) $，优先队列复杂度比暴力更优

稠密图中，$ m=\mathcal{O}(n^2) $，暴力复杂度反而更优

代码

typedef pair<int, int> pii;

int dis[NV], S;
bool vis[NV];

void Dijkstra() {
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[S] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push(make_pair(0, S));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = hd[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            int c = e[i].c;
            if (dis[v] > dis[u] + c) {
                dis[v] = dis[u] + c;
                q.push(make_pair(dis[v], v));
            }
        }
    }
}

void Dijkstra_BF() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[S] = 0;
    // 每次循环能标记一个点
    for (int iV = 1; iV < n; iV++) {
        int min_dis = INF;
        int u;
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && dis[i] < min_dis) {
                min_dis = dis[i];
                u = i;
            }
        }
        vis[u] = true;
        for (int i = hd[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            int c = e[i].c;
            if (dis[v] > dis[u] + c) {
                dis[v] = dis[u] + c;
            }
        }
    }
}