由于Dijkstra每个点被“操作”完了后就鈈会再进行对其他点的松弛操作而SPFA会入队多次,这就造成了它们在最短路计数实现上的不同
先说Dijkstra的思路给每个点记一个ans[i]表示源点到当湔点最短路的条数
这个是非常好理解的,正确性也显然——每个点只会对其他点最多松弛1次
而SPFA不能直接套用,一个显然的例子是
若直接套用会输出3读者自行手玩一下就会发现,节点2的ans多次加到了4身上。
那怎么改进呢一种可行的方式是对于ans数组和now(当前队首),在now进行松弛操作后清零now的ans
若从当前点now走最短路到对应点vis有三种方式,清零的意义就在于使得每次对vis产生的修改都是1而不是1,2,2或1,2,3。