最短路径

定义

最短路径是指在图中从一个顶点到另一个顶点之间，边权和最小的路径。

• 单源最短路：从一个源点出发，求到所有其他点的最短距离。
• 单终点最短路：求所有点到一个特定终点的最短距离。
• 点对点最短路：求两个特定点之间的最短距离。
• 全源最短路：求所有点对之间的最短距离。

重要概念

最优子结构

最短路径的子路径也是最短路径。

三角不等式

定义 $\delta(a, b)$ 为 $a$ 到 $b$ 的最短距离，对任意三个顶点 $u, v, x$，满足： $\delta(u, v) \le \delta(u, x) + \delta(x, v)$

绕道不会比直达更近（“道”指最短路，不是边）。

这个性质要求不能有负环。

松弛操作（Relaxation）

对于边 $u \to v$（权值 $w$），维护距离估计 $d[v]$（当前已知的从源点到 $v$ 的最短距离上界）。 $d[u] + w < d[v] \xRightarrow{} d[v] \leftarrow d[u] + w$

试试从 $u$ 借道能不能让到 $v$ 的距离更短。

上界性

• 初始 $d[s] = 0$ 且其他为 $+\infty$
• 始终有 $d[v] \ge \delta(s, v)$。

收敛性

当 $d[u] = \delta(s, u)$ 且对边 $(u, v)$ 松弛后，$d[v]$ 会收敛到 $\delta(s, v)$。

负权边

一条边的权值为负数。例如：$A \to B$ 权值 -5。

• Dijkstra 不能处理负权边（会错误地提前确定某些点）。
• Bellman-Ford / SPFA 可以处理负权边，只要没有负环。

负权环（负环）

一个环的总权值为负数。

• 如存在源点可达的负环，可以反复绕这个环，使路径长度趋近于 $-\infty$。

• 此时最短路径问题无定义（或为 $-\infty$）。

负环检测时，负环可能不可达，可以加入一个“超级源点”连接所有点

前驱点

路径上某个点的前一个节点，通过前驱点可以溯源整条路径。

存储

• 单源：前驱点数组 $prev$，$prev[v]$ 是 $v$ 的前驱点
• 全源：前驱点矩阵 $prev$，$prev[u][v]$ 是 $u$ 到 $v$ 的路径上 $v$ 的前驱点

输出

• 按照前驱点回溯，直到源点
• 把路径上的点记录并翻转

单源

int prev[];
void getPath(int a){
    // 临时路径数组
    vector<int> path;
    // 一路回溯到原点（prev[s] == -1） 
    while(a != -1){
        path.push_back(a);
        a = prev[a];
    }
    // 翻转路径输出
    reverse(path.begin(), path.end());
    for(int i: path) cout << i << " ";
}

全源

int prev[][];
vector<int> getPath(int u, int v){
    vector<int> path;
    while(u != v){
        path.push_back(v);
        v = prev[u][v];
    }
    path.push_back(u);
    reverse(path.begin(), path.end());
    return path;
}

实现算法

Dijkstra 算法

Floyd-Warshall 算法

Bellman-Ford 算法

SPFA 算法

附录

Node定义

struct Node {
    int v, w;
    // 构造函数
    Node(int v, int w) : v(v), w(w) {}
};

Edge定义

struct Edge {
    int u, v, w;
    // 构造函数
    Edge(int u, int v, int w) : u(u), v(v), w(w) {}
};