-
Notifications
You must be signed in to change notification settings - Fork 0
/
path_shortest.go
278 lines (247 loc) · 8.42 KB
/
path_shortest.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
package graph
import (
"math"
. "github.com/niluan304/leetcode/container"
)
// Floyd
// 是一种多源点最短路径算法,返回任意两点间的最短距离。
//
// 可以处理有向图或负数边权(但不支持负权回路)
//
// Floyd算法 又称为插点法,寻找给定的加权图中多源点之间最短路径的算法。
// Floyd算法的本质是动态规划
// 最大距离初始化为 math.MaxInt/2
//
// 复杂度
// - 时间复杂度:O(n^3)。
// - 空间复杂度:O(n^2)。
func Floyd(n int, init func(path [][]int)) [][]int {
path := make([][]int, n)
for i := range path {
path[i] = make([]int, n)
for j := range path[i] {
path[i][j] = math.MaxInt / 2 // 初始化最大距离, /2 防止加法溢出
}
path[i][i] = 0
}
// 设置 path[i][j] 两点的边权
init(path)
// 迭代更新以 [0, n-1] 为中转节点的最短距离
for mid := 0; mid < n; mid++ { // mid 为中转节点
for i := 0; i < n; i++ {
if mid == i {
continue
}
for j := 0; j < n; j++ {
if mid == j {
continue
}
path[i][j] = min(path[i][j], path[i][mid]+path[mid][j])
}
}
}
return path
}
// FloydDFS
// Floyd 的本质是动态规划
// [带你发明 Floyd 算法:从记忆化搜索到递推(Python/Java/C++/Go/JS/Rust)](https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/solutions/2525946/dai-ni-fa-ming-floyd-suan-fa-cong-ji-yi-m8s51)
//
// ## 题意解读
//
// 对于城市 $i$,求出 $i$ 到其余城市的最短路长度,统计有多少个最短路长度 $\le \textit{distanceThreshold}$,把个数记作 $\textit{cnt}_i$。
//
// 例如示例 1,$\textit{cnt}_0=2,\textit{cnt}_1=3,\textit{cnt}_2=3,\textit{cnt}_3=2$。
//
// 其中 $\textit{cnt}_i$ 最小的 $i$ 就是答案。示例 1 中的城市 $0$ 和城市 $3$ 对应的 $\textit{cnt}_i$ 都是最小的,这种情况返回 $0$ 和 $3$ 的最大值,即 $3$。
//
// 为了解决本题,我们需要求出**任意两个城市之间的最短路长度**。
//
// ## 前置知识:动态规划入门
//
// 请看视频讲解 `b23.tv/pc522x3`
//
// ## 一、启发思考:寻找子问题
//
// ![lc1334-c.png](https://pic.leetcode.cn/1699881511-DbyZrc-lc1334-c.png)
//
// ## 二、递归怎么写:状态定义与状态转移方程
//
// 定义 $\textit{dfs}(k,i,j)$ 表示从 $i$ 到 $j$ 的最短路长度,并且这条最短路的中间节点编号都 $\le k$。注意中间节点不包含 $i$ 和 $j$。
//
// 根据上面的讨论:
//
// - 不选 $k$,那么中间节点的编号都 $\le k-1$,即 $\textit{dfs}(k,i,j) = \textit{dfs}(k-1,i,j)$。
// - 选 $k$,问题分解成从 $i$ 到 $k$ 的最短路,以及从 $k$ 到 $j$ 的最短路。由于这两条最短路的中间节点都不包含 $k$,所以中间节点的编号都 $\le k-1$,故得到 $\textit{dfs}(k,i,j)=\textit{dfs}(k-1,i,k)+\textit{dfs}(k-1,k,j)$。
//
// 这两种情况取最小值,就得到了 $\textit{dfs}(k,i,j)$。写成式子就是
//
// $$
// \textit{dfs}(k,i,j) = \min (\textit{dfs}(k-1,i,j), \textit{dfs}(k-1,i,k)+\textit{dfs}(k-1,k,j))
// $$
//
// 递归边界:$\textit{dfs}(-1,i,j) = w[i][j]$。$k=-1$ 表示 $i$ 和 $j$ 之间没有任何中间节点,此时最短路长度只能是连接 $i$ 和 $j$ 的边的边权,即 $w[i][j]$。如果没有连接 $i$ 和 $j$ 的边,则 $w[i][j]=\infty$。
//
// 递归入口:$\textit{dfs}(n-1,i,j)$,表示从 $i$ 到 $j$ 的最短路长度。$k=n-1$ 是因为本题节点编号为 $0$ 到 $n-1$,任意最短路的中间节点编号都 $\le n-1$。
// ### 复杂度分析
//
// - 时间复杂度:$\mathcal{O}(n^3)$。
// - 空间复杂度:$\mathcal{O}(n^2)$。
//
// ## 思考题
//
// 向图中添加一条边,如何维护 $f$ 数组?
//
// 最暴力的做法是,每次添加一条边,就用 $\mathcal{O}(n^3)$ 时间全部重算一遍。有没有更快的做法呢?
//
// 这题是 [2642. 设计可以求最短路径的图类](https://leetcode.cn/problems/design-graph-with-shortest-path-calculator/)
//
// ---
//
// 欢迎关注 [B站@灵茶山艾府](https://space.bilibili.com/206214)
//
// 更多精彩题解,请看 [往期题解精选(已分类)](https://github.com/EndlessCheng/codeforces-go/blob/master/leetcode/SOLUTIONS.md)
func FloydDFS(n int, init func(path [][]int)) [][]int {
path := make([][]int, n)
for i := range path {
path[i] = make([]int, n)
for j := range path[i] {
path[i][j] = math.MaxInt / 2 // 初始化最大距离, /2 防止加法溢出
}
path[i][i] = 0
}
// 设置 path[i][j] 两点的边权
init(path)
cache := make([][][]*int, n)
for i := 0; i < n; i++ {
cache[i] = make([][]*int, n)
for j := 0; j < n; j++ {
cache[i][j] = make([]*int, n)
}
}
// dfs(k,i,j)表示 i-j 的最短路且路径中节点的编号不超过 k 的 min
// dfs(k,i,j) = min(dfs(k-1,i,j), dfs(k-1,i,k)+dfs(k-1,k,j))
var dfs func(k, i, j int) int
dfs = func(k, i, j int) (res int) {
if k == -1 {
return path[i][j]
}
ptr := &cache[i][j][k]
if *ptr != nil {
return **ptr
}
defer func() { *ptr = &res }()
return min(
dfs(k-1, i, j),
dfs(k-1, i, k)+dfs(k-1, k, j),
)
}
// 迭代更新以 [0, n-1] 为中转节点的最短距离
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
if i != j {
path[i][j] = dfs(n-1, i, j)
}
}
}
return path
}
type DijkstraEdge struct {
To int
Weight int
}
// Dijkstra
// 单源最短路径算法,返回起点 start 到其他节点的最短路径
// Dijkstra 算法是一种贪心算法,不支持负数边权
//
// 暴力解法求最短路长度最小的节点,适用于稠密图
//
// 复杂度
// - 时间复杂度:O(n^2)。
// - 空间复杂度:O(n^2)。
func Dijkstra(n int, start int, init func(graph [][]DijkstraEdge)) (distance, from []int) {
graph := make([][]DijkstraEdge, n)
// 初始化 graph[i] 的邻接表
init(graph)
visit := make([]bool, n)
from = make([]int, n)
distance = make([]int, n)
for i := 0; i < n; i++ {
distance[i] = math.MaxInt / 2 // 初始化最大距离 /2 防止加法溢出
from[i] = -1 // -1 表示无法到达
}
distance[start] = 0 // 初始化
// 计算从起始节点到所有其他节点的最短距离
for {
cur := -1 // 初始化
// 在未访问节点中,找到距离起始节点最近的节点
for i, ok := range visit {
if !ok && (cur == -1 || distance[i] < distance[cur]) {
cur = i
}
}
// 如果没有找到最近的未访问节点,则退出循环
if cur == -1 {
break
}
// 标记当前节点为已访问
visit[cur] = true
// 更新当前节点邻居到起点的最短距离
for _, edge := range graph[cur] {
to := edge.To
d := edge.Weight + distance[cur]
if distance[to] > d {
distance[to] = d
from[to] = cur
}
}
}
return distance, from
}
// DijkstraHeap
// 单源最短路径算法,返回起点 start 到其他节点的最短路径
// Dijkstra 算法是一种贪心算法,不支持负数边权
//
// 通过「最小堆」维护最短路长度最小的节点,适合稀疏图
//
// 复杂度
// - 时间复杂度:O(mlogm)。
// - 空间复杂度:O(m)。
func DijkstraHeap(n int, start int, init func(graph [][]DijkstraEdge)) (distance, from []int) {
graph := make([][]DijkstraEdge, n)
// 初始化 graph[i] 的邻接表
init(graph)
distance = make([]int, n)
from = make([]int, n)
for i := 0; i < n; i++ {
distance[i] = math.MaxInt / 2 // 初始化最大距离 /2 防止加法溢出
from[i] = -1 // -1 表示无法到达
}
distance[start] = 0 // 初始化
type Pair struct{ To, Distance int }
hp := NewEmptyHeap(func(x, y Pair) bool {
return x.Distance < y.Distance // 最小堆
})
hp.Push(Pair{To: start, Distance: 0}) // 初始化
// 计算从起始节点到所有其他节点的最短距离
for !hp.Empty() {
// 在未访问节点中,找到距离起始节点最近的节点
head := hp.Pop()
cur := head.To
// 下面循环中的 d < distance[i] 可能会把重复的节点 i 入堆
// 也就是说,堆中可能会包含多个相同节点,且这些相同节点的 distance 值互不相同
// 那么这个节点第二次及其后面出堆的时候,由于 distance[cur] 已经更新成最短路了,可以直接跳过
if head.Distance > distance[cur] {
continue
}
for _, edge := range graph[cur] {
to := edge.To
d := edge.Weight + distance[cur]
if distance[to] > d {
distance[to] = d
from[to] = cur
hp.Push(Pair{To: to, Distance: d})
}
}
}
return distance, from
}