关于SPFA的几个问题
  • 板块学术版
  • 楼主Remarks
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/11/15 20:54
  • 上次更新2023/11/4 00:27:39
查看原帖
关于SPFA的几个问题
321529
Remarks楼主2021/11/15 20:54

如果有特意构造数据的负权单元最短路问题,我能不能用知乎问答的第二个回答中所提到各种SPFA优化办法来 一定的分数?如果可以的话,哪种更容易骗到更多的分数?

LLL 优化:每次将入队结点距离和队内距离平均值比较,如果更大则插入至队尾。
SLF 优化:每次将入队结点距离和队首比较,如果更大则插入至队尾。
SLF 带容错:每次将入队结点距离和队首比较,如果比队首大超过一定值则插入至队尾。
mcfx 优化:在第 [L,R] 次访问一个结点时,将其放入队首,否则放入队尾。通常取 [L=2,R=√V] 
SLF + swap:每当队列改变时,如果队首距离大于队尾,则交换首尾。
2021/11/15 20:54
加载中...