提高级-图论算法-单源次短路

# 单源次短路

---

## 定义

单源次短路径指的是在某个无向图 $G = (V, E) $ 中， 给定某个源点 $v_1$, 由 $v_1$ 到其他顶点的所有路径中长度为次短的路径。单源次短路径问题是单源 $k$ 最短路径问题的特例。对于一般的单源 $k$ 最短路径问题，可以通过扩展 $Dijkstra $ 或 $Bellman-Ford$ 算法来求解。

---

## 分类

单源次短路径区分严格次短和非严格次短，其中非严格次短路径的长度可以与最短路径的长度相同，只是路径中的顶点序列不同。

---
## 流程

记边 $(v_i,v_j)$的权值为 $w_{i,j} $ 。算法的时间复杂度为 $O((m+n)\log n) $。 算法的流程如下。
1. 置 $S=\empty$, $T=V$。
2. 求解出从$v_1$ 到其他顶点 $v_i$ 的最短路径 $P_i$ 及其长度 $d_i$。
3. 对每个顶点 $v_i \ne v_1$，枚举与 $v_i$ 邻接但不在 $P_i$ 中的顶点 $v_{i\'}$ ，计算 $f_i = \min\limits_{(v_i,v_{i'}) \in E, v_{i'} \notin P_i}(d_{i'} + w_{i', i})$。如果不存在这样的顶点，则置 $f_i$ 为足够大的数值。
4. 从 $T$ 中选取 $f_{i*}$ 值最小的顶点 $v_{i*}$，将其加入到 $S$ 中并从 $T$ 中删除。
5. 对 $v_i$ 所关联的每一条边 $(v_i, v_j)$ ，若 $v_j \in T $ 则在边 $(v_i,v_j)$ 上做松弛操作，同时更新 $f_i$ 的值。
6. 重复步骤 4 和 5， 直到 $S$ 中包含了目标顶点 $v_k$ 或者包含了所有顶点为止。

算法终止时的 $f_i$ 即为顶点为 $v_i$ 到源点 $v_1$ 的次短路径长度 ($1 \le i \le n$) 。 在求解单源严格次短路径时，需要在步骤 2  中 严格 限定 $f_i \gt d_i $.

---
## 代码示例

```c
// dis : 从源点到各顶点的最短路径长度数组
// f   : 从源点到各顶点的次短路径长度数组
// head: 邻接表表头数组，其中 head[u] 为结点 u 的邻接表表头
// e   : 邻接表结构体，其中 e[i].nxt 指向下一条边，e[i].w 为边权
void SecondShortestPath()
{
    for (int i = 1; i <= n; i++)
        dis[i] = INF; // 源点S 到顶点i的最短路径长度
    dis[S] = 0;
    Dijkstra(dis); // 计算出最短路数组
    for(int u = 1; u <= n; u++)
        f[u] = INF; // 源点 S 到 u 的次短路径长度
    for(int u = 1; u <= n; u++)
        for(int i = head[u];i;i = e[i].nxt)
        {
            int v = e[u].tv;
            if(dis[u] + e[i].w < f[v] && dis[u] + e[i].w > dis[v])
                             f[v] = dis[u] + e[i].w;
        }
    // 求解得到部分次短路
    Dijkstra(f); // 用类似最短路的松弛操作得到最终结构 
}
```