type
status
date
slug
summary
tags
category
icon
password
@ZZHow(ZZHow1024)
图的最短路径问题：
- 单源最短路
- 所有边权都是正数
- 朴素 Dijkstra 算法
- 堆优化版 Dijkstra 算法
- 存在负权边
- Bellman-Ford 算法
- SPFA 算法
- 多源汇最短路
- Floyd 算法
朴素 Dijkstra
迪杰斯特拉算法采用的是一种贪心的策略。进行 n 次迭代去确定每个点到起点的最小值，最后输出的终点的即为我们要找的最短路的距离。
堆优化版 Dijkstra
对朴素版 Dijkstra 进行优化，在时间复杂度最高的寻找距离最短的点 时可以使用小根堆优化，Java 语言可使用优先队列(PriorityQueue)，配合自定义的 Pair 类实现。
bellman-ford
迭代 次，每次循环所有边，更新路径：
dist[b] = min(dist[b], dist[a] + w);（松弛操作）。全部操作完后满足三角不等式：SPFA
针对 bellman-ford 算法的
dist[b] = Math.min(dist[b], backup[a] + w); 使用队列进行优化。Floyd
基于动态规划。枚举 更新路径：
d(i, j) = min(d(i, j), d(i, k) + d(k, j));