迪杰斯特拉 & 堆优化

博文

---

单源最短路

该博客的单源最短路算法要解决的就是在一个没有负权边的图上，找出所有点与源点 $s$ 的最短路径，这样一个问题。这里介绍迪杰斯特拉 $O(n^2)$ 解法与堆优化 $O(m\log m)$ 解法，其中 $n$ 为图上节点数量，$m$ 为图上边的数量。
不介绍也不推荐玄学复杂度的 $spfa$ 解法。

朴素写法思路：贪心

1. 首先将所有点与源点的距离设为无穷大（记录在 $dis$ 数组中），$s$ 与自己的距离初始化为 $0$，还有一个表示“已经确定最短路径长度”的节点集合 $Set$。
2. 然后不断从不属于 $Set$ 集合的点中找到一个 $dis$ 最小的点 $x$，那么这个点在以后的操作中一定不会再更新（由于边权非负，所以如果后面最短路径将通过其他点 $y$ 到达 $x$，那么这个值最小为 $dis_y+dis_{y\rightarrow\cdots\rightarrow x}\geq dis_y$，由于 $dis_y\geq dis_x$，所以可以保证在后续运行过程中 $dis_x$ 不会被更新为更小的值），将这个点加入集合 $Set$ 中，然后更新所有与 $x$ 相邻节点的 $dis_t$ 为 $\min(dis_t,dis_x+dis_{x\rightarrow t})$。
3. 不断重复第二步，直到所有点的最短路径都被找到 / 所有点都在 $Set$ 集合中。

朴素写法时间复杂度

从上面的算法可以看出，大循环要将所有点都加入集合一次，而每次寻找这个“不在集合中且 $dis_x$ 最小的点”需要一次 $O(n)$ 的循环，接着更新所有与 $x$ 邻接的点（最多有 $n$ 个点），这里也需要 $O(n)$，所以大循环为 $O(n)$，小循环为 $O(n+n)$，整体时间复杂度为 $O(n\times(n+n))=O(n^2)$。

$O(n^2)$ 代码

const int maxn = 1000 + 100;
struct Node {
    int pos;
    int dis;
    Node() {}
    Node(int p, int d) {
        pos = p;
        dis = d;
    }
};
int n;
int dis[maxn];
bool vis[maxn];
vector<Node> G[maxn];
void dij(int s) {
    // 距离初始化
    fill(dis, dis + n + 1, INT_MAX);
    dis[s] = 0;
    int cnt = n;
    // cnt 表示不在集合中的节点个数
    while(cnt > 0) {
        int Min = INT_MAX;
        int x;
        // 寻找不在集合中的，距离 s 最近的节点
        for(int i = 1; i <= n; ++i) {
            if(!vis[i] && dis[i] < Min) {
                Min = dis[i];
                x = i;
            }
        }
        // 将节点 x 加入集合
        --cnt;
        vis[x] = true;
        // 更新节点 x 的邻接节点
        int len = G[x].size();
        for(int i = 0; i < len; ++i) {
            int pos = G[x][i].pos;
            int d = G[x][i].dis;
            dis[pos] = min(dis[pos], dis[x] + d);
        }
    }
}

堆优化

上面能够优化的时间复杂度是在“找到不在集合中的离 $s$ 最近的点”（每个点必须要进入集合才算更新结束，所以大循环的 $O(n)$ 是无法减小的），我们能否通过一些排序操作，使得能够快速地找到这个点 $x$ 呢？
这里就可以用到一个“小顶堆”的数据结构，它能够在 $O(\log n)$（其中 $n$ 为堆中的元素数量）的时间复杂度内完成插入、删除最小值的操作，在 $O(1)$ 的时间复杂度内完成取堆内最小值的操作。于是我们可以将上面的查找这一步操作放入到堆中，时间复杂度就能下降到 $O(\log n)$。
但这里要注意一点，在我们查找之后，是可以更新这个点的最短距离的，但是小顶堆不允许访问、更改堆内元素，只能访问堆顶元素，所以如果将点与当前最短距离放入堆内，将存在一些多余的点（更新时该点还未从堆顶弹出），而这些所有数据最多有 $m$ 个，$m$ 为图上边的数量。
这里可以标记某个点 $x$ 已经在 $Set$ 集合中，这样在其他指向 $x$ 的点更新到 $x$ 的时候，就不必再重复判断。
但是这种做法是多余的，因为如果 $x$ 已经在 $Set$ 集合中，则指向 $x$ 的 $y$ 点必然无法更新 $dis_x$ 的值，所以实际上可以放任不管。

堆优化时间复杂度

从上面可以看出，这个代码应该类似于 $bfs$ 的代码，只是将队列改为优先队列（小顶堆），这样就能保证优先弹出的是距离 $s$ 最短的（但不能保证不在集合 $Set$ 中），整体的大循环应该是每个点都进入队列（不只一次）然后出队列，这个次数由图上的边数决定，为 $O(m)$（其中 $m$ 为图上边的数量），而在堆中，最多会被存放 $m$ 个数据点，所以小循环内应该是 $O(\log m)$，所以整体的时间复杂度为 $O(m\log m)$。

$O(m\log m)$ 代码

const int maxn = 1000 + 100;
struct Node {
    int pos;
    int dis;
    Node() {}
    Node(int p, int d) {
        pos = p;
        dis = d;
    }
};
// 由于优先队列默认为大顶堆，所以重载小于号要用 a.dis > b.dis，来起到小顶堆的作用
bool operator<(const Node &a, const Node &b) {
    return a.dis > b.dis;
}
int n;
int dis[maxn];
vector<Node> G[maxn];
priority_queue<Node> que;
void dij(int s) {
    // 初始化距离
    fill(dis, dis + n + 1, INT_MAX);
    dis[s] = 0;
    que.push(Node(s, 0));
    while(!que.empty()) {
        Node tmp = que.top();
        que.pop();
        // 更新节点 tmp 的邻接节点，若邻接节点被更新，则将节点和 dis 加入小顶堆
        int len = G[tmp.pos].size();
        for(int i = 0; i < len; ++i) {
            int pos = G[tmp.pos][i].pos;
            int d = G[tmp.pos][i].dis;
            if(dis[pos] > tmp.dis + d) {
                dis[pos] = tmp.dis + d;
                que.push(Node(pos, dis[pos]));
            }
        }
    }
}

两种写法的比较

两种写法最大的区别在于时间复杂度，第一种是 $O(n^2)$，第二种是 $O(m\log m)$，在大多数情况下都可以用第二种写法（例如题目给出 $m$ 的数据范围在 $[1,10^6]$ 内），但是在节点数 $n$ 比较大的完全图（完全图的边数为 $m=C_n^2=\frac{n\times(n-1)}{2}$，）下，第二种的时间复杂度就为 $O(n^2\log n^2)$，这样第二种写法的时间复杂度就会比第一种大，在 $n$ 超过 $1000$ 时，完全图情况下就只能用第一种写法，因此朴素写法并不是没有用的。

队列写法

在刚学 $dij$ 的时候，可能大家都是从 $bfs$ 过渡过来的，所以看到别人的 $dij$ 思路时，都会用队列实现，但是很容易写挫，这里先搬上队列写法（和堆优化写法很像）再讨论讨论这种写法：

const int maxn = 1000 + 100;
struct Node {
    int pos;
    int dis;
    Node() {}
    Node(int p, int d) {
        pos = p;
        dis = d;
    }
};
int n;
int dis[maxn];
vector<Node> G[maxn];
queue<Node> que;
void dij(int s) {
    dis[s] = 0;
    que.push(Node(s, 0));
    while(!que.empty()) {
        Node tmp = que.front();
        que.pop();
        int len = G[tmp.pos].size();
        for(int i = 0; i < len; ++i) {
            int pos = G[tmp.pos][i].pos;
            int d = G[tmp.pos][i].dis;
            if(dis[pos] > dis[tmp.pos] + d) {
                dis[pos] = dis[tmp.pos] + d;
                que.push(Node(pos, dis[pos]));
            }
        }
    }
}

这段代码没有什么注释，是因为……我现在已经看不懂这段代码了（虽然是我写的并且过了题目），这段代码的实际时间复杂度的表达式我不知道是什么，最坏时间复杂度也不知道（数据构造得好的话运行次数将超过 $n^2$）。
这里给出一个四个节点的完全图邻接链表表示：

A → [B,100] → [C,10] → [D,1]
B → [A,100] → [C,1] → [D,1]
C → [A,10] → [B,1] → [D,1]
D → [A,1] → [B,1] → [C,1]

如果在上面这个邻接链表上跑，从 $A$ 点开始，点进入队列的顺序依次为

$$A[0]\rightarrow B[A,100]\rightarrow C[A,10]\rightarrow D[A,1]\rightarrow B[C,11]\rightarrow B[D,2]\rightarrow C[D,2]$$
其中 $X[Y,t]$ 表示点 $X$ 的距离 $dis_X$ 被点 $Y$ 更新为 $t$ 后进入队列。
由于是四个节点的完全图，所以每个节点出队列后都要“尝试”更新另外三个节点（即使用 $vis$ 数组标记，但在某个节点出队列时仍然需要进行依次“尝试”判断该点是否可以更新，也被计为一次操作），所以总共需要 $21$ 次操作，大于 $n^2=4^2=16$ 次操作。
个人认为，在这段代码中，节点 $x$ 和 $dis_x$ 进入队列的条件不充分，或者说，在那个条件下进入队列是没有依据的，如果按照这种方式进入队列，很有可能先访问到一个比较远的点，然后这个比较远的点先出了队列，不断对后面的点做无效的更新，而比较近的点后出队列，又要重新更新这些点。上面的数据让点 $B~C$ 重复进入队列是由于 $B$ 点先出队列做了一次无效的更新，而 $C$ 点也做了一次无效的更新，最后 $D$ 点的更新才是有效的。注意这里的更新是无效的，而上面的第一、二种写法就不会出现这种无效的更新，正是这种无效的更新，使得这种写法的时间复杂度无法（或者我还不会）用表达式表示出来。
我认为这种写法能够通过大多数题目，是因为大多数题目的数据较为随机，没有去构造卡这种写法的数据，所以在大多数随机情况下，这种写法的时间复杂度可以用 $O(n^2)$ 近似。
以上是对于用普通队列写法的个人观点，与我有不同观点的，欢迎在评论区赐教。