最短路问题
如果一个无环无向图，且边为等权重，从起始点u到终点v，计算最短路径，可以用广度优先搜索算法（Breadth First Search，BFS）求得。如果一个图是无环无向，但是边是加权的，且存在负值，广度优先搜索难以解决。基于此，Dijkstra算法和Bellman-Ford算法，用于求解边为非等权重和权重带有负值的最短路径问题。单源路径最短问题是指从一个起点到所有点。
BFS
BFS求解无权图最短路径问题模板
from collections import deque
def bfs_shortest(graph, start, end, n):
dist = [–1] * n
dist[start] = 0
queue = deque([start])
while queue:
u = queue.popleft()
for v in graph[u]:
if dist[v] == –1: # 未访问
dist[v] = dist[u] + 1
if v == end:
return dist[v]
queue.append(v)
return –1
接下来将介绍Dijkstra算法Bellman-Ford算法。
Dijkstra算法
Dijkstra算法是用于求解带权重的有向图上单源最短路径问题，要求所有边的权重非负。算法核心是维护一个节点集合S，从源节点s到该集合中的每个节点之间的最短距离都被找到。之后重复从V-S中选择最短路径的节点u加入到集合S中，直到V-S为空集。算法模板如下：
def dijkstra(start: int, n: int , graph: List[List[tuple[int,int]]]):
# graph[u] = [(w1,v1)，(w2,v2),…]表示父节点u指向下一个节点v的权重为w
dist = [float('inf') for _ in range(n)]
visited = [False] * n
dist[start] = 0
h = [] # 集合 V – S
heapq.heappush(h,(0,start))
while h:
# 从集合 V – S 中找出，距离最小的值
d, u = heapq.heappop(h)
if visited[u] == True:
continue
# 把距离的最小值加入到结合 S 中
visited[u] = True
for w,v in graph[u]:
if dist[u] + w < dist[v] :
dist[v] = dist[u] + w
# 放入到 结合 V – S 中
heap.heappush(h,[dist[v], v])
return dist
Bellman-Ford算法
Bellman-Ford算法解决的是一般情况下的单源最短路径问题，边的权重可以为负值。Bellman-Ford的核心思想在于，对于任意一个具有n个节点的图G，任意两点之间的最短路径最多包含n-1条边。
def bellman_ford(graph: list[list[tuple[int,int]]],start:int):
# graph[u] = [(w1,v1)，(w2,v2),…]表示父节点u指向下一个节点v的权重为w,其中w可能为负
n = len(graph)
dist = [float('inf') for _ in range(n)]
p = [None for _ in range(n)]
dist[start] = 0
# 遍历节点
for i in range(n – 1):
# 遍历节点指向的下一条边
for u, edges in enumerate(graph):
for w, v in edges:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
# v的前驱节点为u
p[v] = u
for u,edges in enumerate(graph):
for w, v in edges:
# 负环检测，如果是有负环的话，不存在最短路径
if dist[v] > dist[u] + w:
return None
return dist, p
Floyd
Dijkstra和Bellman-Ford算法求解的都是从一个起点到其他点的最短路径，Floyd算法则是一次性求解出所有点对之间的最短距离。适用于求解多源最短路径问题，图中任意两点之间的最短路径，因为复杂度太高，不适用于求解点数太多的图。Floyd算法的核心是枚举一个中转点k，判断从i到j经过k是否会更短。其转移公式可用下式描述：
d
i
s
t
[
i
]
[
j
]
=
m
i
n
(
d
i
s
t
[
i
]
[
j
]
,
d
i
s
t
[
i
]
[
k
]
+
d
i
s
t
[
k
]
[
j
]
)
dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j])
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]) 原本从i到j的距离和i先到k再到j的距离，哪一个更短，就保留谁。
def floyd(n,edges):
# n 为节点个数
# edgs 为边，储存格式为(u, v, w)
# 使用三个 for 循环，找到最小值
INF = float('inf')
dist = [[INF]* n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u,v,w in edges:
dist[u][v] = min(dist[u][v],w)
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
def floyd_with_path(n, edges):
# n 为节点个数
# edgs 为边，储存格式为(u, v, w)
# 不仅返回最小值，还返回最短路径
INF = float('inf')
dist = [[INF] for _ in range(n)]
next_node = [[–1] * n for _ in range(n)]
for u,v,w in range(n):
if w < dist[u][v]:
dist[u][v] = w
next_node[u][v] = v
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] != INF and dist[k][j] != INF:
dist[i][j] = dist[i][k] + dist[k][j]
next_node[i][j] = next_node[i][k]
def get_path(next_node, start, end):
if next_node[start][end] == –1:
return []
path = [start]
while start != end:
start = next_node[start][end]
path.append(start)
return path
相关题目
743.网络延迟时间
743. 网络延迟时间 – 力扣（LeetCode）
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
示例 1：
**输入：**times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 **输出：**2
示例 2：
**输入：**times = [[1,2,1]], n = 2, k = 1 **输出：**1
示例 3：
**输入：**times = [[1,2,1]], n = 2, k = 2 输出：-1
提示：
- 1 <= k <= n <= 100
- 1 <= times.length <= 6000
- times[i].length == 3
- 1 <= ui, vi <= n
- ui != vi
- 0 <= wi <= 100
- 所有 (ui, vi) 对都 互不相同（即，不含重复边）
解析：构造图graph的格式，用 Dijstra算法求解
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) –> int:
# 构造图 graph
graph = [[] for _ in range(n)]
for u, v, w in times:
graph[u – 1].append((w, v – 1))
dist = [float('inf') ] * n
dist[k – 1] = 0
visited = [False] * n
h = []
# 以dist 作为 小堆根 的排序
heapq.heappush(h, (0, k – 1))
while h:
d, u = heapq.heappop(h)
if visited[u]:
continue
# 把距离的最小值加入到结合 S 中
visited[u] = True
for w, v in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(h, (dist[v], v))
max_dist = max(dist)
return –1 if max_dist == float('inf') else max_dist
773.滑动谜题
773. 滑动谜题 – 力扣（LeetCode） 在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
示例 1：
**输入：**board = [[1,2,3],[4,0,5]] **输出：**1 **解释：**交换 0 和 5 ，1 步完成
示例 2:
**输入：**board = [[1,2,3],[5,4,0]] 输出：-1 **解释：**没有办法完成谜板
示例 3:
**输入：**board = [[4,1,2],[5,0,3]] **输出：**5 解释： 最少完成谜板的最少移动次数是 5 ， 一种移动路径: 尚未移动: [[4,1,2],[5,0,3]] 移动 1 次: [[4,1,2],[0,5,3]] 移动 2 次: [[0,1,2],[4,5,3]] 移动 3 次: [[1,0,2],[4,5,3]] 移动 4 次: [[1,2,0],[4,5,3]] 移动 5 次: [[1,2,3],[4,5,0]]
提示：
- board.length == 2
- board[i].length == 3
- 0 <= board[i][j] <= 5
- board[i][j] 中每个值都 不同
解析
对于最短路径问题，BSF是远远优于DFS的，对于BFS而言，只要任意一个节点扩散到目的状态，此时肯定是最短路，可以直接返回。但是DFS需要将所有的可能路径枚举完后才可以确认最短路径。
将二维的状态转为一维的，让问题更加方便处理。例如
[[1,2,3],
[4,5,0]]
转为[1,2,3,4,5,0]
同通过 0 的位置，确认棋盘可能转换的状态。例如当 0 在第一个位置时，
[[0,2,3],
[4,5,1]]，
可以转为的位置为[1,3]
class Solution:
def slidingPuzzle(self, board: list[list[int]]) –> int:
dirs = [[1,3], [0,2,4], [1,5],
[0,4], [1,3,5], [2,4]]
# 展平
q_init = [board[0] + board[1],0]
q = deque([q_init])
vst = set()
vst.add( (tuple(board[0]) + tuple(board[1])) )
# 开始BFS搜索
while q:
start, steps = q.popleft()
if start == [1, 2, 3, 4, 5, 0]: return steps
# 找到 0 的索引
zero_index = start.index(0)
for next_dir in dirs[zero_index]:
# 要用到复制
new_start = start[:]
new_start[zero_index], new_start[next_dir] = new_start[next_dir], new_start[zero_index]
new_start_tuple = tuple(new_start)
if new_start_tuple not in vst:
vst.add(new_start_tuple)
q.append([new_start, steps + 1])
return –1
1334.阈值距离内邻居最少的城市
1334. 阈值距离内邻居最少的城市 – 力扣（LeetCode）
输入：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
输出：0
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是：
城市 0 -> [城市 1]
城市 1 -> [城市 0, 城市 4]
城市 2 -> [城市 3, 城市 4]
城市 3 -> [城市 2, 城市 4]
城市 4 -> [城市 1, 城市 2, 城市 3]
城市 0 在阈值距离 2 以内只有 1 个邻居城市。
提示：
- 2 <= n <= 100
- 1 <= edges.length <= n * (n – 1) / 2
- edges[i].length == 3
- 0 <= fromi < toi < n
- 1 <= weighti, distanceThreshold <= 10^4
- 所有 (fromi, toi) 都是不同的。
解析
要求得任意两个节点之间的距离，是多源最短路径，n的上限是 100 ，所有可以用Floyd算法求解
代码：
class Solution:
def findTheCity(self, n: int, edges: list[list[int]], distanceThreshold: int) –> int:
INF = float('inf')
dist = [[INF] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0
for u, v ,w in edges:
dist[u][v] = w
dist[v][u] = w
for k in range(n):
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
res = float('inf')
min_city = float('inf')
# 要求返回的编号最大
# for i in range(n):
# cnt = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold)
# if cnt <= min_city :
# min_city = cnt
# if res > i:
# res = i
for i in range(n):
cnt = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold)
if cnt <= min_city:
min_city = cnt
res = i
return res
