003 ベルマンフォード法

下記の有向グラフでのノードAから各ノードまでの最短距離を
ベルマンフォード法で求めます。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    struct GraphInfoDef
    {
        internal char FromPos;
        internal char ToPos;
        internal int Kyori;
    }

    static void Main()
    {
        var GraphInfoList = new List<GraphInfoDef>();
        GraphInfoList.Add(new GraphInfoDef() { FromPos = 'A', ToPos = 'B', Kyori = 4 });
        GraphInfoList.Add(new GraphInfoDef() { FromPos = 'A', ToPos = 'D', Kyori = 2 });
        GraphInfoList.Add(new GraphInfoDef() { FromPos = 'B', ToPos = 'C', Kyori = 1 });
        GraphInfoList.Add(new GraphInfoDef() { FromPos = 'C', ToPos = 'F', Kyori = 6 });
        GraphInfoList.Add(new GraphInfoDef() { FromPos = 'D', ToPos = 'C', Kyori = 1 });
        GraphInfoList.Add(new GraphInfoDef() { FromPos = 'D', ToPos = 'E', Kyori = 4 });
        GraphInfoList.Add(new GraphInfoDef() { FromPos = 'E', ToPos = 'F', Kyori = 5 });

        BellmanFord(GraphInfoList);
    }

    //ベルマンフォード法で各ノードまでの最短距離を求める
    static void BellmanFord(List<GraphInfoDef> pGraphInfoList)
    {
        //各ノードまでの距離のDict
        var SumKyoriDict = new Dictionary<char, int>();
        SumKyoriDict.Add('A', 0);

        //ノード数-1だけループする
        for (int I = 1; I <= pGraphInfoList.Count - 1; I++) {
            bool IsUpdated = false;

            foreach (char EachKey in SumKyoriDict.Keys.ToArray()) {
                //そのノードから訪問可能なノードで
                //最短距離を更新可能なら更新
                List<GraphInfoDef> wkGraphList =
                    pGraphInfoList.FindAll(X => X.FromPos == EachKey);
                foreach (GraphInfoDef EachGraphInfo in wkGraphList) {
                    int wkSumKyori = SumKyoriDict[EachKey] + EachGraphInfo.Kyori;
                    if (SumKyoriDict.ContainsKey(EachGraphInfo.ToPos))
                        if (SumKyoriDict[EachGraphInfo.ToPos] <= wkSumKyori)
                            continue;
                    SumKyoriDict[EachGraphInfo.ToPos] = wkSumKyori;
                    IsUpdated = true;
                }
            }
            if (IsUpdated == false) break;
        }
        foreach (var EachPair in SumKyoriDict.OrderBy(X => X.Value)) {
            Console.WriteLine("{0}までの最短距離は{1}", EachPair.Key, EachPair.Value);
        }
    }
}

実行結果

Aまでの最短距離は0
Dまでの最短距離は2
Cまでの最短距離は3
Bまでの最短距離は4
Eまでの最短距離は6
Fまでの最短距離は9

解説

各ノードまでの最短距離をDictionaryで管理してます。