关于最短路
  • 板块学术版
  • 楼主sunyizhe还是MC大佬
  • 当前回复7
  • 已保存回复7
  • 发布时间2024/7/3 13:06
  • 上次更新2024/7/3 15:52:24
查看原帖
关于最短路
481330
sunyizhe还是MC大佬楼主2024/7/3 13:06

众所周知,Dij 用优先队列+vis 数组,Spfa 用队列。 所以,知周所众,Dij 去掉 vis 数组和把 Spfa 的队列改为优先队列其实是一个东西。

所以蒟蒻有几个问题:

  1. 这两个算法本质上是一个东西吗?
  2. Spfa 是能被卡的,那这种 Spfa 会被卡吗?如果会,那说明 Dij 的 vis 数组起到了很重要的作用。为什么 Dij 不会被卡?(除负数边权)
  3. 这种“新型算法”分别相对于 Dij 和 Spfa 的速度怎样? 望大佬解答,谢谢!!
2024/7/3 13:06
加载中...