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);
}