spfa和dijkstra的区别
本质的区别就是st数组代表的含义不同
- spfa表示该点是否已在队列中,如果已在,就不要重复更新了
- dij则表示该点是否已经加入了集合
代码上最大的区别就是
dijkstra
int y = tmp.second;
for(auto i:son[y])
{
if(dist[i.first]>dist[y]+i.second)
{
dist[i.first] = dist[y]+i.second;
}
if(!st[i.first])
q.push({dist[i.first],i.first});
}
spfa
for(auto i:son[tmp])
{
if(dist[i.first]>dist[tmp] +i.second )
{
dist[i.first]=dist[tmp] +i.second;
if(!st[i.first])
st[i.first] = true , q.push(i.first);
}
}