ベルマン・フォード法

今回はベルマン・フォード法をやっていきます。

使用する問題は下記URLのものを使います。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=ja

まず、入力から

INF=10**9
V,E,r=map(int,input().split())
Graph=[list(map(int,input().split())) for _ in range(E)]
dist=[INF]*(V)
dist[r]=0#始点は0

ダイクストラ法とあまり変わらないです。

処理部分を書いていきます

for i in range(V):
    for s,t,d in Graph:
            if dist[s]+d<dist[t]:#最短距離を更新するかどうか
                dist[t]=dist[s]+d#最短距離を更新
                if i==V-1:#負の閉路を検出
                    print("NEGATIVE CYCLE")
                    exit()

ベルマン・フォード法を使うメリットは負の閉路を検出できることにあるので、そこの処理の解説をしていきます。
今回の問題の入力例2で負の閉路があるのでそれを使います。
まず図に表わすと以下のようになります。

入力例2

入力例2では1-2-3と通ることでどんどん最短距離を更新をしてしましい、ここに負の閉路があることがわかる。
なので、負の閉路を検出する方法としてv-1以上ループするならそれは負の閉路と判断されます。
なぜなら、始点から各頂点を訪れるためのに通る辺の数はv-1となるため。
始点を除いた頂点の数はv-1となります。そこをすべて訪れる辺の数もv-1となります。
それ以上ループすると負の閉路が存在することになり、永遠に処理がおわりません。
説明が下手でごめんなさい。

コード全体

INF=10**9
V,E,r=map(int,input().split())
Graph=[list(map(int,input().split())) for _ in range(E)]
dist=[INF]*(V)
dist[r]=0


for i in range(V):
    for s,t,d in Graph:
            if dist[s]+d<dist[t]:#最短距離を更新するかどうか
                dist[t]=dist[s]+d#最短距離を更新
                if i==V-1:#負の閉路を検出
                    print("NEGATIVE CYCLE")
                    exit()
                    
for i in dist:
    if i==INF:
        print("INF")
    else:
        print(i)

参考記事
https://qiita.com/ageprocpp/items/cdf67e828e1b09316f6e#%E3%83%99%E3%83%AB%E3%83%9E%E3%83%B3%E3%83%95%E3%82%A9%E3%83%BC%E3%83%89%E6%B3%95
https://wakabame.hatenablog.com/entry/2017/09/06/221400
http://nishiharayuugo.blog.fc2.com/blog-entry-14.html