SPFA

今天复习 SPFA 算法，发现自己的代码只能过70的数据，代码中对于 $st$ 的判断的位置存在问题。

事实上，应该先遍历对于 ver 的邻接节点，先试图更新其邻接节点 $j$ ，然后判断 $j$ 是否在队列中——即判断 ${st}_{j}==true$，如果不在则添加进队列。

chat回答

错误版本分析

1. 在检查是否更新邻接节点的距离之前就先检查 st[j]。如果节点已经被处理过（st[j]为1），就跳过这个节点，导致一些节点可能没有得到正确的更新。
2. 在更新节点距离后，即使 st[j] 已经为1，依然会将这个节点加入到优先队列中，这可能导致重复处理相同的节点，增加算法运行时间。

if(st[j])continue;  // 如果已经在队列中，则跳过
if(dist[j]>dist[ver]+w[i]){
    dist[j]=dist[ver]+w[i];
    heap.push({dist[j],j});
    st[j]=1;
}

正确版本分析

正确版本中的 dijkstra() 函数实现避免了上述问题：

1. 不是先检查 st[j]，而是先更新距离，然后再根据 st[j] 的状态决定是否要将节点加入到优先队列中。
2. 这种处理确保每个节点的最短距离只在它最初被发现时加入优先队列，避免了重复处理。

if(dist[j]>dist[ver]+w[i]){
    dist[j]=dist[ver]+w[i];
    if(!st[j]){  // 只有当节点不在队列中时，才加入队列
        heap.push({dist[j],j});
        st[j]=1;
    }
}