spfa_dfs的优化
spfa_dfs的优化
spfa的朴素优化
void spfa(Node){
instack[Node] = true;
for(Node,v) in E:
if dis[v]>dis[Node]+edge(Node,v)){
dis[v] = dis[Node]+edge(Node,v);
if not instack[v] {
spfa(v);
}else{
return;
}
}
instack[Node] = false;
}spfa的限制修改优化
void spfa_init(node){
for(node,v) in e
if dis[node] + edge(node,v)<dis[v]{
dis[v] = dis[node] + edge(node,v);
spfa_init(v);
return true;
}
return false;
}
main{
for node in v:
while spfa_init(node);
for node in v:
spfa(node);
}
查看6道真题和解析
