代码随想录算法训练营 Day 53
Published:
Q1. KamaCoder 97
Floyd算法：动态规划找到图中任意两个点的最短距离，可以出现权重为负的边，但不能出现负权回路
- 确定dp数组：dp[i][j][k]表示起点为i，终点为j，中间节点出现在[1,k]这个区间内
- 确定递推公式：1. 路径经过节点k，$dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]$；2. 不经过节点k，$dp[i][j][k] = dp[i][j][k-1]$
- 数组初始化：要找最短路径，因此初始化为最大值。然后给定边(i, j), 初始化dp[i][j][0]和dp[j][i][0]为给定权重
- 确定遍历顺序：从前往后遍历，k在最外层（理解原因）
if __name__ == '__main__':
n, m = map(int, input().split())
grid = [[[float('inf')] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
for _ in range(m):
n1, n2, w = map(int, input().split())
grid[n1][n2][0] = w
grid[n2][n1][0] = w
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
grid[i][j][k] = min(grid[i][j][k - 1], grid[i][k][k - 1] + grid[k][j][k - 1])
q = int(input())
for _ in range(q):
src, dst = map(int, input().split())
if grid[src][dst][-1] == float('inf'):
print(-1)
else:
print(grid[src][dst][-1])
可以看到k次循环的取值只与k-1次有关，压缩dp数组
if __name__ == '__main__':
n, m = map(int, input().split())
grid = [[float('inf')] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
n1, n2, w = map(int, input().split())
grid[n1][n2] = w
grid[n2][n1] = w
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j])
q = int(input())
for _ in range(q):
src, dst = map(int, input().split())
if grid[src][dst] == float('inf'):
print(-1)
else:
print(grid[src][dst])
Q2. KamaCoder 127
$A^*$算法：利用启发式思想，缩小BFS的搜索范围。按照距离进行排序，而距离可以分为两部分：已经走过的距离和离终点的距离。但到终点的距离其实是未知的，只能通过启发式算法进行估算
如果是无权图（边的权值都是1） 那就用广搜，代码简洁，时间效率和 dijkstra 差不多（具体要取决于图的稠密） 如果是有权图（边有不同的权值），优先考虑 dijkstra。 $A^*$算法关键在于启发式函数， 也就是影响广搜或者 dijkstra 从容器（队列）里取元素的优先顺序。
import heapq
directions = [(1, 2), (2, 1), (-1, 2), (2, -1), (1, -2), (-2, 1), (-1, -2), (-2, -1)]
def distance(a, b):
return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5
def bfs(src, dst):
pq = [(distance(src, dst), src)]
step = {src:0}
while pq:
d, curr = heapq.heappop(pq)
if curr == dst:
return step[curr]
for dx, dy in directions:
nx = curr[0] + dx
ny = curr[1] + dy
if 1 <= nx <= 1000 and 1 <= ny <= 1000:
new_step = step[curr] + 1
if new_step < step.get((nx, ny), float('inf')):
step[(nx, ny)] = new_step
heapq.heappush(pq, (distance((nx, ny), dst) + new_step, (nx, ny)))
return -1
if __name__ == '__main__':
n = int(input())
for _ in range(n):
src_x, src_y, dst_x, dst_y = map(int, input().split())
s = bfs((src_x, src_y), (dst_x, dst_y))
print(s)