AlgorithmAndLeetCode · pull · Jun 10, 2025 · Jun 10, 2025 · Jun 10, 2025 · Jun 10, 2025
diff --git a/Contents/08.Graph/04.Graph-Shortest-Path/04.Graph-Multi-Source-Shortest-Path.md b/Contents/08.Graph/04.Graph-Shortest-Path/04.Graph-Multi-Source-Shortest-Path.md
@@ -0,0 +1,202 @@
+## 1. 多源最短路径简介
+
+> **多源最短路径（All-Pairs Shortest Paths）**：对于一个带权图 $G = (V, E)$，计算图中任意两个顶点之间的最短路径长度。
+
+多源最短路径问题的核心是找到图中任意两个顶点之间的最短路径。这个问题在许多实际应用中都非常重要，比如：
+
+1. 网络路由中的路由表计算
+2. 地图导航系统中的距离矩阵计算
+3. 社交网络中的最短关系链分析
+4. 交通网络中的最优路径规划
+
+常见的解决多源最短路径问题的算法包括：
+
+1. **Floyd-Warshall 算法**：一种动态规划算法，可以处理负权边，但不能处理负权环。
+2. **Johnson 算法**：结合了 Bellman-Ford 算法和 Dijkstra 算法，可以处理负权边，但不能处理负权环。
+3. **重复 Dijkstra 算法**：对每个顶点运行一次 Dijkstra 算法，适用于无负权边的图。
+
+## 2. Floyd-Warshall 算法
+
+### 2.1 Floyd-Warshall 算法的算法思想
+
+> **Floyd-Warshall 算法**：一种动态规划算法，通过逐步考虑中间顶点来更新任意两点之间的最短路径。
+
+Floyd-Warshall 算法的核心思想是：
+
+1. 对于图中的任意两个顶点 $i$ 和 $j$，考虑是否存在一个顶点 $k$，使得从 $i$ 到 $k$ 再到 $j$ 的路径比已知的从 $i$ 到 $j$ 的路径更短
+2. 如果存在这样的顶点 $k$，则更新从 $i$ 到 $j$ 的最短路径
+3. 通过考虑所有可能的中间顶点 $k$，最终得到任意两点之间的最短路径
+
+### 2.2 Floyd-Warshall 算法的实现步骤
+
+1. 初始化距离矩阵 $dist$，其中 $dist[i][j]$ 表示从顶点 $i$ 到顶点 $j$ 的最短路径长度
+2. 对于每对顶点 $(i, j)$，如果存在边 $(i, j)$，则 $dist[i][j]$ 设为边的权重，否则设为无穷大
+3. 对于每个顶点 $k$，作为中间顶点：
+   - 对于每对顶点 $(i, j)$，如果 $dist[i][k] + dist[k][j] < dist[i][j]$，则更新 $dist[i][j]$
+4. 重复步骤 3，直到考虑完所有可能的中间顶点
+5. 返回最终的距离矩阵
+
+### 2.3 Floyd-Warshall 算法的实现代码
+
+```python
+def floyd_warshall(graph, n):
+    # 初始化距离矩阵
+    dist = [[float('inf') for _ in range(n)] for _ in range(n)]
+
+    # 设置直接相连的顶点之间的距离
+    for i in range(n):
+        dist[i][i] = 0
+        for j, weight in graph[i].items():
+            dist[i][j] = weight
+
+    # 考虑每个顶点作为中间顶点
+    for k in range(n):
+        for i in range(n):
+            for j in range(n):
+                if dist[i][k] != float('inf') and dist[k][j] != float('inf'):
+                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
+
+    return dist
+```
+
+代码解释：
+
+1. `graph` 是一个字典，表示图的邻接表。例如，`graph[0] = {1: 3, 2: 4}` 表示从节点 0 到节点 1 的边权重为 3，到节点 2 的边权重为 4。
+2. `n` 是图中顶点的数量。
+3. `dist` 是一个二维数组，存储任意两点之间的最短路径长度。
+4. 首先初始化距离矩阵，将对角线元素设为 0，表示顶点到自身的距离为 0。
+5. 然后设置直接相连的顶点之间的距离。
+6. 主循环中，对于每个顶点 $k$，考虑它作为中间顶点时，是否能缩短其他顶点之间的距离。
+7. 最终返回的距离矩阵中，$dist[i][j]$ 表示从顶点 $i$ 到顶点 $j$ 的最短路径长度。
+
+### 2.4 Floyd-Warshall 算法复杂度分析
+
+- **时间复杂度**：$O(V^3)$
+  - 需要三层嵌套循环，分别遍历所有顶点
+  - 因此总时间复杂度为 $O(V^3)$
+
+- **空间复杂度**：$O(V^2)$
+  - 需要存储距离矩阵，大小为 $O(V^2)$
+  - 不需要额外的空间来存储图的结构，因为使用邻接表表示
+
+Floyd-Warshall 算法的主要优势在于：
+
+1. 实现简单，容易理解
+2. 可以处理负权边
+3. 可以检测负权环（如果某个顶点到自身的距离变为负数，说明存在负权环）
+4. 适用于稠密图
+
+主要缺点：
+
+1. 时间复杂度较高，不适用于大规模图
+2. 空间复杂度较高，需要存储完整的距离矩阵
+3. 不能处理负权环
+
+## 3. Johnson 算法
+
+### 3.1 Johnson 算法的算法思想
+
+> **Johnson 算法**：一种结合了 Bellman-Ford 算法和 Dijkstra 算法的多源最短路径算法，可以处理负权边，但不能处理负权环。
+
+Johnson 算法的核心思想是：
+
+1. 通过重新赋权，将图中的负权边转换为非负权边
+2. 对每个顶点运行一次 Dijkstra 算法，计算最短路径
+3. 将结果转换回原始权重
+
+### 3.2 Johnson 算法的实现步骤
+
+1. 添加一个新的顶点 $s$，并添加从 $s$ 到所有其他顶点的边，权重为 0
+2. 使用 Bellman-Ford 算法计算从 $s$ 到所有顶点的最短路径 $h(v)$
+3. 重新赋权：对于每条边 $(u, v)$，新的权重为 $w(u, v) + h(u) - h(v)$
+4. 对每个顶点 $v$，使用 Dijkstra 算法计算从 $v$ 到所有其他顶点的最短路径
+5. 将结果转换回原始权重：对于从 $u$ 到 $v$ 的最短路径，原始权重为 $d(u, v) - h(u) + h(v)$
+
+### 3.3 Johnson 算法的实现代码
+
+```python
+from collections import defaultdict
+import heapq
+
+def johnson(graph, n):
+    # 添加新顶点 s
+    new_graph = defaultdict(dict)
+    for u in graph:
+        for v, w in graph[u].items():
+            new_graph[u][v] = w
+        new_graph[n][u] = 0  # 从 s 到所有顶点的边权重为 0
+
+    # 使用 Bellman-Ford 算法计算 h(v)
+    h = [float('inf')] * (n + 1)
+    h[n] = 0
+
+    for _ in range(n):
+        for u in new_graph:
+            for v, w in new_graph[u].items():
+                if h[v] > h[u] + w:
+                    h[v] = h[u] + w
+
+    # 检查是否存在负权环
+    for u in new_graph:
+        for v, w in new_graph[u].items():
+            if h[v] > h[u] + w:
+                return None  # 存在负权环
+
+    # 重新赋权
+    reweighted_graph = defaultdict(dict)
+    for u in graph:
+        for v, w in graph[u].items():
+            reweighted_graph[u][v] = w + h[u] - h[v]
+
+    # 对每个顶点运行 Dijkstra 算法
+    dist = [[float('inf') for _ in range(n)] for _ in range(n)]
+    for source in range(n):
+        # 初始化距离数组
+        d = [float('inf')] * n
+        d[source] = 0
+
+        # 使用优先队列
+        pq = [(0, source)]
+        visited = set()
+
+        while pq:
+            current_dist, u = heapq.heappop(pq)
+            if u in visited:
+                continue
+            visited.add(u)
+
+            for v, w in reweighted_graph[u].items():
+                if d[v] > current_dist + w:
+                    d[v] = current_dist + w
+                    heapq.heappush(pq, (d[v], v))
+
+        # 转换回原始权重
+        for v in range(n):
+            if d[v] != float('inf'):
+                dist[source][v] = d[v] - h[source] + h[v]
+
+    return dist
+```
+
+代码解释：
+
+1. `graph` 是一个字典，表示图的邻接表。
+2. `n` 是图中顶点的数量。
+3. 首先添加一个新的顶点 $s$，并添加从 $s$ 到所有其他顶点的边，权重为 0。
+4. 使用 Bellman-Ford 算法计算从 $s$ 到所有顶点的最短路径 $h(v)$。
+5. 检查是否存在负权环，如果存在则返回 None。
+6. 重新赋权，将图中的负权边转换为非负权边。
+7. 对每个顶点运行一次 Dijkstra 算法，计算最短路径。
+8. 将结果转换回原始权重，得到最终的距离矩阵。
+
+### 3.4 Johnson 算法复杂度分析
+
+- **时间复杂度**：$O(VE \log V)$
+  - 需要运行一次 Bellman-Ford 算法，时间复杂度为 $O(VE)$
+  - 需要运行 $V$ 次 Dijkstra 算法，每次时间复杂度为 $O(E \log V)$
+  - 因此总时间复杂度为 $O(VE \log V)$
+
+- **空间复杂度**：$O(V^2)$
+  - 需要存储距离矩阵，大小为 $O(V^2)$
+  - 需要存储重新赋权后的图，大小为 $O(E)$
+  - 因此总空间复杂度为 $O(V^2)$
diff --git a/Contents/08.Graph/04.Graph-Shortest-Path/06.Graph-The-Second-Shortest-Path.md b/Contents/08.Graph/04.Graph-Shortest-Path/06.Graph-The-Second-Shortest-Path.md
@@ -0,0 +1,131 @@
+## 1.1 次短路径简介
+
+> **次短路径**：给定一个带权有向图，求从起点到终点的次短路径。次短路径是指长度严格大于最短路径的所有路径中长度最小的那条路径。
+
+### 1.1.1 问题特点
+
+- 次短路径必须严格大于最短路径
+- 可能存在多条最短路径，但次短路径是唯一的
+- 如果不存在次短路径（如最短路径是唯一的），则返回 $-1$。
+
+### 1.1.2 常见变体
+
+1. 允许重复边的次短路径
+2. 不允许重复边的次短路径
+3. 带约束条件的次短路径（如必须经过某些节点）
+
+## 1.2 次短路径基本思路
+
+求解次短路径的常用方法是使用 Dijkstra 算法的变体。基本思路如下：
+
+1. 使用 Dijkstra 算法找到最短路径。
+2. 在寻找最短路径的过程中，同时维护次短路径。
+3. 对于每个节点，我们需要维护两个距离值：
+   - $dist1[u]$：从起点到节点 u 的最短距离。
+   - $dist2[u]$：从起点到节点 u 的次短距离。
+
+### 1.2.1 具体实现步骤
+
+1. 初始化 $dist1$ 和 $dist2$ 数组，所有值设为无穷大。
+2. 将起点加入优先队列，距离为 $0$。
+3. 每次从队列中取出距离最小的节点 $u$。
+4. 遍历 $u$ 的所有邻接节点 $v$：
+   - 如果找到更短的路径，更新 $dist1[v]$。
+   - 如果找到次短的路径，更新 $dist2[v]$。
+5. 最终 $dist2[终点]$ 即为所求的次短路径长度。
+
+### 1.2.2 算法正确性证明
+
+1. 对于任意节点 $u$，$dist1[u]$ 一定是最短路径长度。
+2. 对于任意节点 $u$，$dist2[u]$ 一定是次短路径长度。
+3. 算法会考虑所有可能的路径，因此不会遗漏次短路径。
+
+## 1.3 次短路径代码实现
+
+```python
+import heapq
+
+def second_shortest_path(n: int, edges: List[List[int]], start: int, end: int) -> int:
+    """
+    计算从起点到终点的次短路径长度
+
+    参数:
+        n: 节点数量
+        edges: 边列表，每个元素为 [起点, 终点, 权重]
+        start: 起始节点
+        end: 目标节点
+
+    返回:
+        次短路径的长度，如果不存在则返回 -1
+    """
+    # 构建邻接表
+    graph = [[] for _ in range(n)]
+    for u, v, w in edges:
+        graph[u].append((v, w))
+
+    # 初始化距离数组
+    dist1 = [float('inf')] * n  # 最短距离
+    dist2 = [float('inf')] * n  # 次短距离
+    dist1[start] = 0
+
+    # 优先队列，存储 (距离, 节点) 的元组
+    pq = [(0, start)]
+
+    while pq:
+        d, u = heapq.heappop(pq)
+
+        # 如果当前距离大于次短距离，跳过
+        if d > dist2[u]:
+            continue
+
+        # 遍历所有邻接节点
+        for v, w in graph[u]:
+            # 计算新的距离
+            new_dist = d + w
+
+            # 如果找到更短的路径
+            if new_dist < dist1[v]:
+                dist2[v] = dist1[v]  # 原来的最短路径变成次短路径
+                dist1[v] = new_dist  # 更新最短路径
+                heapq.heappush(pq, (new_dist, v))
+            # 如果找到次短的路径
+            elif new_dist > dist1[v] and new_dist < dist2[v]:
+                dist2[v] = new_dist
+                heapq.heappush(pq, (new_dist, v))
+
+    return dist2[end] if dist2[end] != float('inf') else -1
+
+# 使用示例
+n = 4
+edges = [
+    [0, 1, 1],
+    [1, 2, 2],
+    [2, 3, 1],
+    [0, 2, 4],
+    [1, 3, 5]
+]
+start = 0
+end = 3
+
+result = second_shortest_path(n, edges, start, end)
+print(f"次短路径长度: {result}")
+```
+
+## 1.4 算法复杂度分析
+
+- 时间复杂度：$O((V + E)\log V)$，其中 $V$ 是节点数，$E$ 是边数。
+- 空间复杂度：$O(V)$，用于存储距离数组和优先队列。
+
+## 1.5 应用场景
+
+1. 网络路由：寻找备用路径。
+2. 交通规划：寻找替代路线。
+3. 通信网络：寻找备用通信路径。
+4. 物流配送：规划备用配送路线。
+
+## 1.6 注意事项
+
+1. 次短路径必须严格大于最短路径。
+2. 如果不存在次短路径，返回 $-1$。
+3. 图中可能存在负权边，此时需要使用 Bellman-Ford 算法的变体。
+4. 对于无向图，需要将每条边都加入两次。