(自学笔记,基本上可以算是抄一些网上的笔记,只是用来记录自己的学习成果,但没有他人的学习价值,甚至可能出现理解错误)
(后期整体学完后,可能会写一些适合学习的笔记,像上篇还没来得及干完的DFS笔记)
最短路算法概念:找出两点之间的最短路距离.
概念 特点1 特点2 单源最短路 从任意起点出发,到达固定终点的最短距离 未知 未知 多源最短路 从任意顶点出发,到达任意重点的最短距离 未知 未知
松弛:
选择一个顶点作为"中转站",经过比较后,更改与其相邻顶点的最短路径值:
单源最短路:
设置数组a:
a[j]用来存储从起点到顶点j的最短距离
单源最短路松弛:
选择一个顶点k作为松弛顶点:(j为路径终点)
w[i,j]代表顶点i到顶点j的权值:
多源最短路:
设置数组a:
a[i][j]用来存储从顶点i到顶点j的最短距离
多源最短路松弛:
i作为起点,k作为中转站,j作为终点:
FLOYD(弗洛伊德):
A29680.最短距离查询【Floyd】:
具体思路:
三层循环:
外层:n个顶点枚举(都做一遍松弛)
中层:n个顶点枚举:找出起点(到松弛顶点的起点)
内层:n个顶点枚举:找出中终点(松弛顶点能到的顶点)
Dijkstra:
Gold King的搬家方案:
