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);
}
全部评论

相关推荐

03-12 21:00
中山大学 Ruby
点赞 评论 收藏
分享
牛客251490824号:你这不去保研找鸡毛工作
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务