# 单源最短路问题

对有权有向图 $G = (V,E)$, 我们定义其路径 $p = \langle v_0,v_1,\dots,v_k \rangle$ 的权 $w(p):=\sum_{i=1}^kw(v_{i-1},v_i)$. 对顶点 $u,v$ 若存在从 $u$ 到 $v$ 的路径，我们定义 $u$ 到 $v$ 的最短路权重 $\delta(u,v) = \min\{w(p)|u\leadsto\!\!\!\!\!\!\!\ ^{^p}\ \ v\}$. 否则，定义 $\delta(u,v) = \infty$. 我们称一条路 $p$ 是最短路 (shortest path)，当且仅当 $w(p) = \delta(u,v)$.

单源最短路 (single-source shortest paths) 问题，就是在已知图 $G=(V,E)$ 及其上的权函数 $w:E \to \mathbb{R}$, 找出某确定的源点 $s \in V$ 到每个顶点 $v \in V$ 的最短路权重 $\delta(s,v)$ 的问题。

# 变体

单源最短路问题存在一些变体，包括：

1. 单终点最短路问题 (single-destination shortest-paths problem)
2. 单对顶点最短路问题 (single-pair shortest-path problem)
3. 每对顶点间最短路问题 (all-pairs shortest-paths problem)

对于前两个问题，采用单源最短路算法仍然是最快的。

# 最短路相关性质

对于最短路，我们有三个最基本的性质：

1. 最短路的子路是最短路
2. 最短路不能包含非零权回路
3. 最短路算法执行后，图 $G$ 的前驱子图 $G_\pi$ 是一棵最短路径树 (shortest-paths tree)。

前两个性质都容易采用反证法证明。性质 3 根据 性质 1 容易推出。

# 松弛技术及性质

在执行松弛技术前，我们需要对图中的顶点进行初始化：

for (Vertex v : V) {

    v.d = Double.POSITIVE_INFINITY;

    v.pi = null;

}

s.d = 0;

初始化过程后，对所有顶点 $v \in V$, 有 $\pi[v] = \text{NIL}$, 对 $v\in V\setminus \{s\}$, 有 $d[v] = \infty$, 且 $d[s] = 0$.

松弛 (relaxation) 是在边 $(u,v)$ 存在的情况下，对点 $v$ 进行的操作。

if (v.d > u.d + w(u,v)) {

    v.d = u.d + w(u,v);

    v.pi = u;

}

该操作实际上是将边$(u,v)$ 纳入最短路考虑的范围内的过程。

# 性质

对松弛操作，存在一些显然的性质：

1. 三角不等式 (triangle inequality): $\forall (u,v) \in E$, $\delta(s,v) \leq \delta(s,u) + w(u,v)$.
2. 上界性质 (upper-bound property): $\forall v$, $d[v] \geq \delta(s,v)$, 且一旦$d[v] = \delta(s,v)$，则$d[v]$ 不再变化 (废话)。
3. 无路径性质 (no-path property): 若从$s$ 到$v$ 不存在路径，则总是有$d[v] = \delta(s,v) = \infty$.
4. 收敛性质 (convergence property): 若$s \leadsto u \to v$ 是图$G$ 中某$u,v \in V$ 的最短路，且在松弛边$(u,v)$ 前$d[u] = \delta(s,u)$，则松弛边$(u,v)$ 后$d[v] = \delta(s,v)$.
5. 路径松弛性质

# 模板

#include <iostream>

#include <vector>

#include <queue>

#include <limits>

using namespace std;

class Graph {

public:

    Graph(int n) : adj(n) {}

    void add_edge(int u, int v, int w);

    void dijkstra(int s, vector<int>& dist, vector<int>& prev);

private:

    vector<vector<pair<int, int>>> adj; // 邻接表

};

void Graph::add_edge(int u, int v, int w) {

    adj[u].push_back(make_pair(v, w));

    adj[v].push_back(make_pair(u, w));

}

void Graph::dijkstra(int s, vector<int>& dist, vector<int>& prev) {

    int n = adj.size();

    dist.assign(n, numeric_limits<int>::max()); // 初始化距离数组

    prev.assign(n, -1); // 初始化前驱数组

    vector<bool> visited(n, false); // 初始化 visited 数组

    dist[s] = 0; // 起点距离为 0

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 小根堆

    pq.push(make_pair(0, s)); // 起点入队

    while (!pq.empty()) {

        int u = pq.top().second;

        pq.pop();

        if (visited[u]) {

            continue; // 已访问过，跳过

        }

        visited[u] = true;

        for (auto& p : adj[u]) {

            int v = p.first;

            int w = p.second;

            if (dist[u] + w < dist[v]) {

                dist[v] = dist[u] + w;

                prev[v] = u;

                pq.push(make_pair(dist[v], v));

            }

        }

    }

}

最基础的模板是 洛谷: P3371 【模板】单源最短路径（弱化版）