网站推广活动策划,怎么建网页,网站后台jsp怎么做分页,游戏源码下载第十一章#xff1a;图论part11
Floyd 算法精讲
Floyd 算法代码很简单#xff0c;但真正理解起原理 还是需要花点功夫#xff0c;大家在看代码的时候#xff0c;会发现 Floyd 的代码很简单#xff0c;甚至看一眼就背下来了#xff0c;但我为了讲清楚原理#xff0c;本…第十一章图论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
if __name__ __main__:max_int 10005 # 设置最大路径因为边最大距离为10^4n, m map(int, input().split())grid [[[max_int] * (n1) for _ in range(n1)] for _ in range(n1)] # 初始化三维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, n1):for i in range(1, n1):for j in range(1, n1):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 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)))最短路算法总结篇
最各个最短路算法有个全面的了解
https://www.programmercarl.com/kamacoder/%E6%9C%80%E7%9F%AD%E8%B7%AF%E9%97%AE%E9%A2%98%E6%80%BB%E7%BB%93%E7%AF%87.html
如果遇到单源且边为正数直接Dijkstra。
至于 使用朴素版还是 堆优化版 还是取决于图的稠密度 多少节点多少边算是稠密图多少算是稀疏图这个没有量化如果想量化只能写出两个版本然后做实验去测试不同的判题机得出的结果还不太一样。
一般情况下可以直接用堆优化版本。
如果遇到单源边可为负数直接 Bellman-Ford同样 SPFA 还是 Bellman-Ford 取决于图的稠密度。
一般情况下直接用 SPFA。
如果有负权回路优先 Bellman-Ford 如果是有限节点最短路 也优先 Bellman-Ford理由是写代码比较方便。
如果是遇到多源点求最短路直接 Floyd。
图论总结
https://www.programmercarl.com/kamacoder/%E5%9B%BE%E8%AE%BA%E6%80%BB%E7%BB%93%E7%AF%87.html
