关于Dijkstra 和 SPFA
  • 板块学术版
  • 楼主LEE114514
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/8/28 10:10
  • 上次更新2024/8/28 12:52:14
查看原帖
关于Dijkstra 和 SPFA
750579
LEE114514楼主2024/8/28 10:10

在做题时有时候会遇到需要图论建模后跑类似最短路思想的算法,但是该如何区分使用 SPFA 还是 Dijkstra?

例如 旅游巴士 一题中在从堆中取出一个 disudis_u 之后,如果不满足 dis>=wdis>=w 的 disdis 执行 dis+=⌈w−disk⌉×kdis+= \lceil \frac{w-dis}{k} \rceil \times k 操作,如何判断此时 Dijkstra 是否可行,即一个点在更新过其他点的最短路后自身的最短路是否会被其他点再次更新?

2024/8/28 10:10
加载中...