# Bellman Ford improvement

###### tags: `演算法`

//v.dep為bfs tree中的depth，在INIT(G,s)裡面算好了
Bellman_Ford(G,w,s){
    INIT(G,s)
    for i=1:|G.V|-1
        relax=false
        for each edge uv in G.E and v.dep==i
            if d[v]>d[u]+w(u,v)
                RELAX(u,v,w)
                relax=true
        if !relax
            for each edge uv in G.E
                if d[v]>d[u]+w(u,v)
                    return false
            break
    return true
}

INIT(G,s){
    for each v in G.V
        v.d=INF
        v.parent=NULL
    s.d=0
    s.dep=0
    Q={} //a FIFO queue
    Q.push(s)
    while(!Q.empty()){
        u=Q.pop()
        for v in G.Adj[u]
            v.dep=u.dep+1
            Q.push(v)
    }
}