一、最短路问题

设给定一个带权有向图 $G = (V, E)$ ，源点为 $s$ ，求 $s$ 到 $G$ 中其他各点之间的最短路径，这类问题称为单源最短路径问题。

记顶点 $s$ 到点 $u$ 的最短路径为 $\delta(u)$ ，正在计算的点 $s$ 到点 $u$ 可能的最短路径为 $d (u)$ 。记边 $(u, v)$ 的权重为 $w (u, v)$ ，路径 $\Gamma$ 的长度为 $w(\Gamma)$ 。

定理（最短路问题的最优子结构性质） 设路径 $\Gamma$ 是点 $u$ 到 $v$ 的最短路径， $p, q$ 在 $\Gamma$ 上，即 $\Gamma:u\to p\overset{\Gamma_{p\to q}}{\longrightarrow}q\to v$ ，则 $\Gamma$ 在 $p$ 和 $q$ 之间的部分 $\Gamma_{p\to q}$ 是 $p$ 到 $q$ 的一条最短路径。
证明：采用反证法。假设 $\Gamma_{p\to q}$ 不是 $p$ 到 $q$ 的最短路径，则取 $p$ 到 $q$ 的最短路径 $\Sigma_{p\to q}$ ，于是 $u$ 到 $v$ 有一条比 $\Gamma$ 更短的路径 $u\to p\overset{\Sigma{p\to q}}{\longrightarrow}q\to v$ ，与 $\Gamma$ 是点 $u$ 到 $v$ 的最短路径矛盾。因此假设不成立，定理证毕。?

二、Dijkstra算法

基本思想

Dijkstra算法要求 $\forall e\in E,w(e)\ge 0$ 。即：图中的边权必为非负值。

(1) 将图 $G$ 的顶点集 $V$ 划分为两个集合 $S$ 和 $V ? S$ ，集合 $S$ 存放已经确定了最短路径的顶点集合。令 $d(u)=\begin{cases}0,&u=s\\+\infty,&u\ne s\end{cases}$ 初始状态时， $S=\emptyset$ 。

(2)不断重复以下过程，直到 $S = V$ 为止：

选择顶点 $u$ ，使得 $d(u)=\min\limits_{v\in V-S}d(v)$ 。
我们断言 $u$ 一定满足 $d(u)=\delta(u)$ ，即 $d (u)$ 是 $s$ 到 $u$ 的最短路径。将 $u$ 并入 $S$ 中，即 $S=S\cup\{u\}$ 。
修改与 $u$ 相连的节点的 $d$ 值（称为“松弛”操作）。 $\forall v\in V-S$ 且 $(u,v)\in E$ ，令 $d(v)=\min\{d(v),d(u)+w(u,v)\}$ 。若 $d (v)$ 确实变小了，则设 $v$ 在 $s$ 到 $v$ 的最短路径中的前驱节点 $\text{prev}(v)=u$ 。最终， $s$ 到 $v$ 的最短路径是 $s,\cdots,\text{prev}(\text{prev}(\text{prev}(v))),\text{prev}(\text{prev}(v)),\text{prev}(v),v$ 。

正确性证明

引理1 设算法第(2)步求出 $u$ 满足 $d(u)=\min\limits_{v\in V-S}d(v)$ ， $s$ 到 $u$ 的路径 $\Gamma(u)=(s,\cdots,\text{prev}(\text{prev}(u)),\text{prev}(u),u)$ ，则 $\Gamma(u)$ 中除了 $u$ 以外所有的节点都属于 $S$ ，即 $s,\cdots,\text{prev}(\text{prev}(u)),\text{prev}(u)\in S$ 。

证明：

归纳基础：当 $S=\emptyset$ 时， $u = s$ ， $\Gamma(s)=(s)$ ，其中除了 $s$ 之外没有节点，所以都属于 $S$ 。

归纳步：假设对 $S=S_k$ 时成立。设 $u$ 满足 $d(u)=\min\limits_{v\in V-S_k}d(v)$ ，观察Dijkstra算法的步骤，当节点 $v$ 的 $\text{prev}$ 值被修改为 $u_k$ ，即 $u_k$ 对节点 $v$ 执行松弛操作时， $u_k$ 必已并入 $S$ 中，即 $\text{prev}(v)\in S$ 。故这里也有 $\text{prev}(u)\in S$ 。将 $\text{prev}(u)$ 作为 $u$ ，由同样的思路可得 $\text{prev}(\text{prev}(u))\in S$ 。不断迭代，可得 $s,\cdots,\text{prev}(\text{prev}(u)),\text{prev}(u)\in S$ 。?

引理2 满足 $d(u)=\min\limits_{v\in V-S}d(v)$ 的顶点 $u$ 一定有 $d(u)=\delta (u)$ 。

证明：

归纳基础：当 $S=\empty$ 时， $d (s) = 0$ ，故一定会选择 $u = s$ ，且 $d(s)=\delta(s)=0$ 成立。

归纳步：设对于 $S=S_k$ 时，结论成立，即 $\forall v\in S$ 有 $d(v)=\delta(v)$ ；要证对于 $S=S_{k+1}=S\cup\{u\}$ 时结论也成立，其中 $u$ 满足 $d(u)=\min\limits_{v\notin S_k,v\in V}d(v)$ 。也就是证明 $d(u)=\delta(u)$ 。

我们认为 $\Gamma(u)=(s,\cdots,\text{prev}(\text{prev}(u)),\text{prev}(u),u)$ 是 $s$ 到 $u$ 的最短路径。我们需要证明不存在更短的路径 $\Gamma'(u)$ 。首先，根据归纳假设，有 $d(\text{prev}(u))=\delta(\text{prev}(u))$ 。而根据算法的步骤有 $d(u)=\min\limits_{p\in S}\{d(p)+w(p,u)\}$ ，因此若存在更短的路径 $\Gamma'$ ，在 $\Gamma'$ 中除了 $u$ 以外一定还有不属于 $S$ 的节点。设从 $\Gamma'$ 上 $s$ 到 $u$ 的第一个不属于 $S$ 的节点是 $w$ ，则 $d(w)\le d(u)$ ，这与 $u$ 满足 $d(u)=\min\limits_{v\notin S_k,v\in V}d(v)$ 矛盾，故假设不成立， $\Gamma$ 就是 $s$ 到 $u$ 的最短路径。?

换言之，将 $u$ 取为 $V ? S$ 中 $d$ 最小的节点保证了 $u$ 的前驱节点一定在 $S$ 中。由于 $S$ 中节点的 $\delta$ 都是确定的，且 $u$ 是 $V ? S$ 中离 $S$ 最近的节点，则 $u$ 的 $\delta$ 值是 $V ? S$ 中最小的，但比 $S$ 中任何节点的 $\delta$ 值要大。
在这里插入图片描述
由引理2，我们令 $S = V$ 可得 $\forall u\in V,d(u)=\delta(u)$ 。因此Dijkstra算法是正确的。

代码实现

伪代码：

Dijkstra(Graph G(V, E), Node s) // s为源点
{
    ?u∈V: d[u] = +∞, vis[u] = false // 初始化
    // d就是已经求出的距离，vis表示u是否在集合S中
    d[s] = 0
    while(S != V)
    {
        u = V - S中d最小的节点
        vis[u] = true
        S = S ∪ {u}
        for(每条以u为起始的边e)
        {
            v = e的终点
            if(d[v] > d[u] + w(e))
            {
                d[v] = d[u] + w(e)
                prev[v] = u // 设置v的前驱节点为u
            }
        }
    }
}

如果采用堆进行优化，在每次d[v]被更新时执行DecreaseKey操作，就可以将复杂度将为 $O(m\log n)$ 。但是C++的priority_queue不支持DecreaseKey，所以需要每次将节点v及其距离d[v]同时放入priority_queue中，使得复杂度升为 $O(m\log m)$ 。

C++代码：

int dis[MAXN]; // d数组
bool vis[MAXN]; // 节点是否在S中

struct node
{
    int u, d;
    bool operator<(const node& o) const
    {
        return d > o.d; // 为了维持小根堆的性质，重载运算符
    }
};

void Dijkstra(int s)
{
    memset(dis, 0x3f, sizeof(dis)); // dis置为正无穷
    dis[s] = 0;
    priority_queue<node> Q; // 堆
    Q.push({s, 0}); // 一开始S={s}
    while(!Q.empty())
    {
        int u = Q.top().u;
        Q.pop();
        if(vis[u]) continue;
        /* 因为priority_queue不支持DecreaseKey，
        每次dis[v]被更新时都要加入堆中，使得同一个v会在堆中出现多次*/
        vis[u] = true;
        for(int e = first[u]; e; e = nxt[e])
        {
            int v = go[e];
            if(dis[v] > dis[u] + val[e])
            // 根据引理2，此时vis[v]一定为false，因为S中的节点最短路长度不可能再被更新
            {
                dis[v] = dis[u] + val[e]; // 松弛操作
                Q.push({v, dis[v]}); // 加入堆中
            }
        }
    }
}

三、Floyd-Warshall算法

基本思想

采用邻接矩阵存图。 $w (i, j)$ 表示点 $i, j$ 之间的边权， $f (i, j)$ 表示 $i, j$ 之间的最短路径。假设节点从 $1$ 到 $n$ 编号。

初始化 $f(i,j)=\begin{cases}0,&i=j\\+\infty,&(i,j)\notin E\\w(i,j),&(i,j)\in E\end{cases}$ 并设点集 $S$ 表示某两点间路径上可能包含的中间点的集合，初始状态为 $S=\emptyset$ 。

将 $k$ 从 $1$ 循环到 $n$ 。对于每一个 $k$ ，当前的 $S=\{1,2,\cdots, k-1\}$ ，而 $f (i, j)$ 这里表示从 $i$ 到 $j$ 只经过集合 $S$ 中的点的最短路径。此时我们将 $k$ 并入集合 $S$ ，并令 $f(i,j)=\min(f(i,j),\ f(i,k)+f(k,j))$ 。到最后 $k = n$ 时， $S = V$ ，那么 $i$ 到 $j$ 的只经过 $S$ 中的节点的最短路径 $f (i, j)$ 就是 $i$ 到 $j$ 的最短路径了。

正确性证明

归纳假设：对于每一个 $k$ ，当 $k$ 并入 $S$ 后 $f (i, j)$ 就是从 $i$ 到 $j$ 只经过 $S=\{1,2,\cdots,k\}$ 中的节点的最短路径。

归纳基础：当 $k = 0$ 时， $f(i,j)=\begin{cases}0,&i=j\\+\infty,&(i,j)\notin E\\w(i,j),&(i,j)\in E\end{cases}$ 显然就是从 $i$ 到 $j$ 不经过任何中间节点的最短路径。

归纳步：假设对于 $k ? 1$ 时成立，即：在进行第 $k$ 步之前 $f (i, j)$ 是从 $i$ 到 $j$ 只经过 $\{1,2,\cdots,k-1\}$ 中的节点的最短路径。则当 $k$ 加入 $S$ 中后， $f (i, j)$ 分两种情况：

(1) 从 $i$ 到 $j$ 只经过 $S=\{1,2,\cdots,k\}$ 中节点的最短路径不经过节点 $k$ ，则 $f (i, j)$ 不改变。
(2) 经过节点 $k$ 。设集合 $S=\{1,2,\cdots,k\}$ 的导出子图为 $G_k$ ，则 $f (i, j)$ 就是 $G_k$ 中从 $i$ 到 $j$ 的最短路径。在 $G_k$ 中应用最短路的最优子结构性质，得知 $i$ 到 $j$ 经过 $k$ 的最短路就是 $i$ 到 $k$ 的最短路连上 $k$ 到 $j$ 的最短路。因此 $f (i, j) = f (i, k) + f (k, j)$ 。

将 $f (i, j) 与 f (i, k) + f (k, j)$ 作比较取较小者，就可以知道最短路是否经过 $k$ 。?

代码实现

时间复杂度 $O(n^3)$ 。

memset(f, 0x3f, sizeof(f)); // f先全部置为正无穷
for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
        f[i][j] = read(); // 读入邻接矩阵
for(int k = 1; k <= n; ++k)
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            f[i][j] = min(f[i][j], f[i][k] + f[k][j]);