[C#] ベルマンフォード法で単一始点最短経路問題を解くための実装方法

ベルマンフォード法とは

ベルマン–フォード法 – Wikipedia

ベルマンフォード法はダイクストラ法と同じく、単一始点の最短経路問題を解くためのアルゴリズムの一種です。開始点からすべての点への最短経路を求めることができます。

ダイクストラ法との違いは以下の2点です。

1. 計算量はダイクストラ法よりもベルマンフォード法のほうが大きい。
2. ベルマンフォード法は負の重みを扱える。

ベルマンフォード法でも負の閉路がある場合、無限に経路を小さくできるので最短経路は求まりませんが、負の閉路が存在することを検知すること自体は可能です。

計算量

ベルマンフォード法の計算量は O(V·E) です。V は頂点数、E は辺数です。優先度付きキューを使ったダイクストラ法が計算量 O((E + V)·logV) で、ベルマンフォード法より高速です

ベルマンフォード法を使うメリットは負の重みを扱える点です。

アルゴリズム

ベルマンフォード法の流れは以下の通りです。

1. すべての頂点へのコストを∞とする。始点のコストを0にする。
2. 頂点数 |V| だけループする
3. 2 のループの中ですべての辺をループする E
4. もし辺の始点までの最短コストが∞なら 2 のループを抜ける
5. もし「辺の終点までの最短コスト > 辺の始点までの最短コスト + 辺のコスト」 なら
6. 辺の終点までの最短コストを更新する

2のループと3のループが入れ子になっているので計算量が O(V·E) になります。

もし負の閉路が存在しないグラフの場合、最短経路は同じ頂点を通らないので |V|-1 回のループを行って、その中で各辺を使う場合の最短コストを考えればよいことになります。なのでたぶん手順 2 のループ数は |V|-1 でもいいと思います。

負の閉路が存在する場合の判定方法

負の閉路が存在する場合、上記手順を行っても最短コストは確定しません。なぜなら負の閉路を何度も通ることで無限にコストを小さくできるためです。この場合最短コストは確定しません。

もし負の閉路が存在しない場合、上記手順 2 以下を何度繰り返しても最短コストは確定されているため更新されません。逆に言えばさらに最短コストが更新される場合は負の閉路が存在するということです。

したがって、負の閉路の判定を行いたい場合、上記アルゴリズムの手順にさらに以下の手順を加えればよいです。

1. 頂点数 |V| だけループする
2. 2 のループの中ですべての辺をループする E
3. もし辺の始点までの最短コストが∞なら 2 のループを抜ける
4. もし「辺の終点までの最短コスト > 辺の始点までの最短コスト + 辺のコスト」 なら
5. 辺の終点までの最短コストを更新し、辺の終点に負の閉路フラグを立てる

基本は上記手順の 2~6 と同じです。違いは最短コストの更新が行われる際に、負の閉路が存在する経路であることを判定するフラグを持っておくことです。

s から g までの最短経路を求めたい場合に、s->g の経路途中に負の閉路が存在しない場合は最短コストが確定します。この場合、6 の更新処理は行われません。

もし負の閉路判定処理の最中に g への最短コストが更新される場合、その経路途上に負の閉路が存在しているため、最短コストが確定しないということがわかります。

C# での実装

では実装してみます。

class BellmanFord
{
    public List<Edge> Edges { get; set; }
    public int V { get; set; }
    public long[] Distances { get; set; }
    public bool[] Negative { get; set; }
    public BellmanFord(int v)
    {
        this.V = v;
        this.Edges = new List<Edge>();
    }

    // 辺の追加
    public void Add(int from, int to, int cost)
    {
        this.Edges.Add(new Edge(from, to, cost));
    }

    // 単一始点最短経路を計算する
    public void CalcDistance(int start)
    {
        // 1. 最短コストを初期化する
        this.Distances = new long[V];
        for (int i = 0; i < V; i++)
        {
            this.Distances[i] = long.MaxValue;
        }
        this.Distances[start] = 0;

        // 2. 頂点数 |V| だけループする
        for (int i = 0; i < this.V; i++)
        {
            // 3. すべての辺をループする
            foreach (var e in this.Edges)
            {
                // 4. 辺の始点までの最短コストが∞ならループを抜ける
                if (this.Distances[e.From] == long.MaxValue) continue;

                // 5. 「辺の終点までの最短コスト > 辺の始点までの最短コスト + 辺のコスト」 なら
                var cost = this.Distances[e.From] + e.Cost;
                if (cost < this.Distances[e.To])
                {
                    // 6. 辺の終点までの最短コストを更新する
                    this.Distances[e.To] = cost;
                }
            }
        }

        // 負の閉路判定処理
        this.Negative = new bool[V];
        for (int i = 0; i < this.V; i++)
        {
            foreach (var e in this.Edges)
            {
                if (this.Distances[e.From] == long.MaxValue) continue;
                var cost = this.Distances[e.From] + e.Cost;
                if (cost < this.Distances[e.To])
                {
                    this.Distances[e.To] = cost;
                    this.Negative[e.To] = true;
                }
            }
        }
    }
    public struct Edge
    {
        public int From { get; set; }
        public int To { get; set; }
        public int Cost { get; set; }
        public Edge(int from, int to, int cost)
        {
            this.From = from;
            this.To = to;
            this.Cost = cost;
        }
    }
}

使い方はまずコンストラクタで頂点数を渡して初期化します。その後、Add() で各辺を追加していきます。

グラフ内のすべての辺を追加し終えたら CalcDistance() で始点を指定して最短コストを計算します。計算結果は Distances に、負の閉路の判定結果は Negative に格納されます。

動作を確認してみる

単一始点最短経路問題

judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=ja

AOJに単一始点最短経路問題があるのでこれで正しく動くか見てみます。

// 入力
var V = sc.ReadInt();
var E = sc.ReadInt();
var R = sc.ReadInt();
var bf = new BellmanFord(V);
for (int i = 0; i < E; i++)
{
    var from = sc.ReadInt();
    var to = sc.ReadInt();
    var d = sc.ReadInt();
    bf.Add(from, to, d);
}

// 計算
bf.CalcDistance(R);
foreach (var res in bf.Distances)
{
    if (res == long.MaxValue)
    {
        Console.WriteLine("INF");
    }
    else
    {
        Console.WriteLine(res);
    }
}

始点から目的地点に到達できない場合は ∞ long.MaxValue になっています。

ACしました。

負のコストがある問題

D – Score Attack

AtCoderに典型問題があります。これは最短コストではなく最大コストを求める問題です。

最大コストを求める場合は各辺のコストの正負を反転して最小コストを求めればいいです。この場合用意した機能自体には何も手を加えなくてOKです。求まった最短コストの正負を反転した値が答えになります。

この問題ではさらに負の閉路が存在する場合があり、その場合は “inf” と出力する必要があります。

ただし注意点があります。負の閉路が存在しても、目的地点への途中に閉路が無ければ無視して答えを求めなければなりません。

var N = sc.ReadInt(); // 頂点数
var M = sc.ReadInt(); // 辺数

var bf = new BellmanFord(N);
for (int i = 0; i < M; i++)
{
    var a = sc.ReadInt() - 1;
    var b = sc.ReadInt() - 1;
    var c = sc.ReadInt();
    // コストは正負を反転しておく
    bf.Add(a, b, -c);
}

bf.CalcDistance(0);

 // 計算結果は正負を反転する
var ans = -bf.Distances[N - 1];

// 0 -> N-1 への経路中に負の閉路がある場合は答えが決まらない
if (bf.Negative[N - 1])
{
    Console.WriteLine("inf");
}
else
{
    Console.WriteLine(ans);
}

無事ACできました。

以上。