Bellman-Ford法: 負の重みのエッジを含むグラフにおける最短経路

Bellman-Ford法は、重み付き有向グラフにおける単一始点の最短径路を解くアルゴリズムのひとつです。 各辺の重みが負でも正しく最短経路を求めることができます。

ダイクストラ法よりも遅いので、全ての辺の重みが非負の場合はダイクストラ法を使うべきです。 すなわち、Bellman-Ford法を使うべきなのは負の重みの辺が存在する場合だけです。

グラフに負閉路 (negative cycle、辺の重みの総和が負になる閉路) が含まれるとき、 その閉路を通過することによりいくらでも重みを小さくできるので最短経路は決まりません。 Bellman-Ford法は負閉路の存在を検出することができます。

Bellman-Ford法では、全ての辺について距離が短くなる経路があるかどうかを判定します。 頂点の数を |V|, 辺の数を |E| とすると、計算量は O(|V| |E|)になります。

計算手順

  1. 初期状態として、始点からの最短距離を、始点は0, それ以外は無限大としておく。
  2. 「全辺について、各頂点の最短距離と思われる値を置き換えていく」操作を |V|-1 回繰り返すと、負の閉路がなければ全頂点の最短距離が決定する。

    3. 負の閉路がなければ、2の操作を繰り返すたびにひとつの頂点は最短距離が求まるので、 |V|-1回の反復によって最短距離がグラフ全体に伝播することになる。

辺ef, df, cf, ce, cd, bd, bc, ac, ab の順に値が更新される場合の例

dg00.txt のグラフ説明

初期状態として、すべてのノードまでの距離を無限大とし、始点までの距離は0とおく。

すべてのエッジについて、そのエッジを通った場合の距離が小さい場合はノードの値を更新する。

上の操作を繰り返す。

上の操作を繰返した結果、目的地までの最短距離が確定する。



辺ef, df, db, cf, ce, cd, bd, bc, ac, ab の順に値が更新される場合の例





dg01.txt説明



初期状態として、すべてのノードまでの距離を無限大とし、始点までの距離は0とおく。



すべてのエッジについて、そのエッジを通った場合の距離が小さい場合はノードの値を更新する。



上の操作を繰り返す。



上の操作を繰り返す。



上の操作を繰り返す。



上の操作を繰り返す。



上の操作を繰り返す。



上の操作を繰り返す。

負の閉路があるので、目的地までの最短距離は求まらない。







負の閉路があるので全ての頂点については最短距離は求まらないが、aからfの最短距離は求まる例





dg02.txt説明



負の閉路がありノードi,g,hまでの最短距離は求まらないが、目的地fまでの最短距離は求まる。







プログラム例 (java)



BellmanFord.java
import java.util.*;
public class BellmanFord {
  static boolean debug = false;
  static class Edge {
    int from, to, cost;
    public Edge(int from,int to,int cost) {
      this.from = from; this.to = to; this.cost = cost;
    }
    public String toString() { return "edge["+from+", "+to+", "+cost+"]"; }
  }
  int MAX_V;
  ArrayList<Edge> edges;
  int[] distance;
  public BellmanFord(int n,int m) {
    MAX_V = n;
    edges = new ArrayList<Edge>();
    distance = new int[n];
  }
  public void addEdge(int from, int to, int cost) {
    edges.add(new Edge(from,to,cost));
  }
  public void shortestPath(int src, int dst) {
    for (int i=0; i<distance.length; i++) distance[i] = Integer.MAX_VALUE;
    distance[src] = 0;
    int count = 0;
    boolean updated = true;
    while (updated) {
      updated = false;
      for (Edge e: edges) {
        if (distance[e.from] != Integer.MAX_VALUE
	    && distance[e.to] > distance[e.from] + e.cost) {
          distance[e.to] = distance[e.from] + e.cost;
          updated = true;
          if (count == MAX_V-1) throw new RuntimeException("negative loop");
        }
      }
      count ++;
    }
  }
  public static void main(String[] args) {
    for (int i=0; i<args.length; i++) {
      if (args[i].equals("-d")) debug = !debug;
    }
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(), m = sc.nextInt();
    BellmanFord bf = new BellmanFord(n, m);
    for (int i=0; i<m; i++) {
      int from = sc.nextInt(), to = sc.nextInt(), cost = sc.nextInt();
      bf.addEdge(from,to,cost);
    }
    int src = sc.nextInt(), dst = sc.nextInt();
    try {
	bf.shortestPath(src,dst);
	System.out.println(bf.distance[dst]);
    } catch (Exception e) {
	System.out.println("negative loop");
    }
    if (debug) {
      for (int i=0; i<bf.MAX_V; i++) System.out.print(bf.distance[i]+" ");
      System.out.println();
    }
  }
}






BellmanFord.javaの実行例
$ javac BellmanFord.java
$ java BellmanFord < dg00.txt
7
$ java BellmanFord < dg01.txt
negative loop
$ java BellmanFord -d < dg00.txt
7
0 5 3 5 4 7 
$ java BellmanFord -d < dg01.txt
negative loop
0 0 -2 1 0 3 
$ java BellmanFord -d < dg02.txt
negative loop
0 5 3 5 4 7 -20 -21 -19 






dg00.txt
6 9
0 1 5
0 2 4
1 2 -2
1 3 1
2 3 2
2 4 1
2 5 4
3 5 3
4 5 4
0 5






dg01.txt
6 10
0 1 5
0 2 4
1 2 -2
1 3 1
2 3 2
2 4 1
2 5 4
3 1 -1
3 5 3
4 5 4
0 5






dg02.txt
9 13
0 1 5
0 2 4
1 2 -2
1 3 1
2 3 2
2 4 1
2 5 4
3 5 3
4 5 4
3 6 -1
6 7 -1
7 8 -1
8 6 -1
0 5







プログラム例 (python)



BellmanFord.py
#!/usr/bin/env python
import sys

Vn = 0
G = [{}]

def setNode(n):
  global G, Vn
  Vn = n
  G = [{} for i in range(Vn)]
def addEdge(s,t,w):
  global G
  G[s][t]=w
def solve(s,t):
  global G, Vn
  distance = [sys.maxsize for i in range(Vn)]
  distance[s] = 0
  count = 0
  updated = True
  while updated:
    updated = False
    for i in range(Vn):
      if distance[i] != sys.maxsize:
        for j in G[i]:
          d = distance[i] + G[i][j]
          if (d < distance[j]):
            distance[j] = d
            updated = True
            if count == Vn-1: raise NameError('negative loop')
    count += 1
  return distance[t]

n,m = map(int,input().split())
setNode(n)
for i in range(m):
  s,t,w = map(int,input().split())
  addEdge(s,t,w)
src, dst = map(int,input().split())
print(solve(src,dst))






BellmanFord.pyの実行例
$ python BellmanFord.py < dg00.txt 
7
$ python BellmanFord.py < dg01.txt  ← 負のループ
Traceback (most recent call last):
  File "/raid/nitta/public_html/lec/BellmanFord/python/BellmanFord.py", line 39, in <module>
    print(solve(src,dst))
  File "/raid/nitta/public_html/lec/BellmanFord/python/BellmanFord.py", line 29, in solve
    if count == Vn-1: raise NameError('negative loop')
NameError: negative loop
$ python BellmanFord.py < dg02.txt  ← 負のループ
Traceback (most recent call last):
  File "/raid/nitta/public_html/lec/BellmanFord/python/BellmanFord.py", line 39, in <module>
    print(solve(src,dst))
  File "/raid/nitta/public_html/lec/BellmanFord/python/BellmanFord.py", line 29, in solve
    if count == Vn-1: raise NameError('negative loop')
NameError: negative loop








アルゴリズムc 演習






提出した後は、正しく提出されていることを

http://nw.tsuda.ac.jp/class/algoC/local/handin/

で必ず確認しておいて下さい。





課題提出〆切は次回の講義の開始時刻です。





課題4b





提出ファイルBellmanFordMap04.txt


コメント欄:ノードsからノードtまでの経路の最短距離


提出先:
「宿題提出Web:アルゴリズムc：課題4b」

http://nw.tsuda.ac.jp/class/algoC/local/handin/up.php?id=kadai4b








次の有向グラフをdg01.txt と同じフォーマットで表現しなさい。
ファイル名は BellmanFordMap04.txt とすること。
ただし、有向エッジの上の数字はノード間の距離を表すものとする。





ノードsからノードtまでの最短距離を答えなさい。
求まらない場合は "undefined" と答えなさい。