代码随想录 day62 第十一章图论part11

server/2025/1/7 23:04:05/

第十一章：图论part11

Floyd 算法精讲

Floyd 算法代码很简单，但真正理解起原理还是需要花点功夫，大家在看代码的时候，会发现 Floyd 的代码很简单，甚至看一眼就背下来了，但我为了讲清楚原理，本篇还是花了大篇幅来讲解。

https://www.programmercarl.com/kamacoder/0097.%E5%B0%8F%E6%98%8E%E9%80%9B%E5%85%AC%E5%9B%AD.html

python">if __name__ == '__main__':max_int = 10005  # 设置最大路径，因为边最大距离为10^4n, m = map(int, input().split())grid = [[[max_int] * (n+1) for _ in range(n+1)] for _ in range(n+1)]  # 初始化三维dp数组for _ in range(m):p1, p2, w = map(int, input().split())grid[p1][p2][0] = wgrid[p2][p1][0] = w# 开始floydfor 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])# 输出结果z = int(input())for _ in range(z):start, end = map(int, input().split())if grid[start][end][n] == max_int:print(-1)else:print(grid[start][end][n])

A * 算法精讲（A star算法）

一般笔试或者面试的时候，不会考察A*，都是会结合具体业务场景问 A*算法，例如：地图导航，游戏开发等等。

其实基础版的A* 并不难，所以大家不要畏惧，理解本篇内容，甚至独立写出代码，大家可以做到，加油

https://www.programmercarl.com/kamacoder/0126.%E9%AA%91%E5%A3%AB%E7%9A%84%E6%94%BB%E5%87%BBastar.html

python">
import heapqn = int(input())moves = [(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.5def bfs(start, end):q = [(distance(start, end), start)]step = {start: 0}while q:d, cur = heapq.heappop(q)if cur == end:return step[cur]for move in moves:new = (move[0] + cur[0], move[1] + cur[1])if 1 <= new[0] <= 1000 and 1 <= new[1] <= 1000:step_new = step[cur] + 1if step_new < step.get(new, float('inf')):step[new] = step_newheapq.heappush(q, (distance(new, end) + step_new, new))return Falsefor _ in range(n):a1, a2, b1, b2 = map(int, input().split())print(bfs((a1, a2), (b1, b2)))