dat59 |dijk小根堆 和 bellman
在 dijk 求最小路径的过程中我们每次会选择离集合最近的一个点加入进去,并且更新和这个点相连的所有距离。
- 一个优化方法是在我们维持一个小根堆表示离集合最近的点,
- 取出最近的点,然后将更新后的距离重新加入的小根堆里面
- 一个问题就是一个点对应的不同距离会重复加入到小根堆中,我们通过 visited 数组进行判断过滤。
bellman 算法
- 维护的是一个边集合
- 我们从 1 号点出发,遍历边集合内的所有边,更新点的所有距离mindist
- 由于边给的顺序不同,理论上来说最完美的顺序可以一次得到最短距离,而最差我们可以得到所有和 1 号点相连一条边的最短距离
- 我们距离 n 号点共有n-1条边,也就是无论如何我们只要遍历 n 次所有集合的边就必定能得到最短距离
- 一个剪枝操作就是当我们遍历所有边都没有进行更新操作的时候可以及时跳出
- 时间复杂度是n*e