8-13 最短距離問題

問題

キッチナーからペンブロークまでの経路のリストと、距離の合計を、
全て列挙する

ソース

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

class Program
{
    struct GraphDef
    {
        internal string FromPos;
        internal string ToPos;
        internal int Kyori;
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal string GenzaiPos;
        internal string Path;
        internal int SumKyori;
    }

    static void Main()
    {
        var GraphArr = new GraphDef[11];
        GraphArr[0].FromPos  = "キッチナー"  ; GraphArr[0].ToPos  = "トロント"    ; GraphArr[0].Kyori  = 105;
        GraphArr[1].FromPos  = "キッチナー"  ; GraphArr[1].ToPos  = "バリー"      ; GraphArr[1].Kyori  = 155;
        GraphArr[2].FromPos  = "ノースベイ"  ; GraphArr[2].ToPos  = "ペンブローク"; GraphArr[2].Kyori  = 220;
        GraphArr[3].FromPos  = "ペンブローク"; GraphArr[3].ToPos  = "オタワ"      ; GraphArr[3].Kyori  = 150;
        GraphArr[4].FromPos  = "バリー"      ; GraphArr[4].ToPos  = "トロント"    ; GraphArr[4].Kyori  =  90;
        GraphArr[5].FromPos  = "トロント"    ; GraphArr[5].ToPos  = "ベルビル"    ; GraphArr[5].Kyori  = 190;
        GraphArr[6].FromPos  = "ベルビル"    ; GraphArr[6].ToPos  = "オタワ"      ; GraphArr[6].Kyori  = 230;
        GraphArr[7].FromPos  = "ベルビル"    ; GraphArr[7].ToPos  = "ペンブローク"; GraphArr[7].Kyori  = 230;
        GraphArr[8].FromPos  = "バリー"      ; GraphArr[8].ToPos  = "ハンツビル"  ; GraphArr[8].Kyori  = 125;
        GraphArr[9].FromPos  = "ハンツビル"  ; GraphArr[9].ToPos  = "ノースベイ"  ; GraphArr[9].Kyori  = 130;
        GraphArr[10].FromPos = "ハンツビル"  ; GraphArr[10].ToPos = "ペンブローク"; GraphArr[10].Kyori = 245;

        var stk = new Stack<JyoutaiDef>();
        var AnswerList = new List<JyoutaiDef>();

        JyoutaiDef WillPush;
        WillPush.Level = 1;
        WillPush.GenzaiPos = "キッチナー";

        for (int I = 0; I <= GraphArr.GetUpperBound(0); I++) {
            if (GraphArr[I].FromPos == "キッチナー") {
                WillPush.GenzaiPos = GraphArr[I].ToPos;
                WillPush.Path = "キッチナー" + "," + GraphArr[I].ToPos;
                WillPush.SumKyori = GraphArr[I].Kyori;
                stk.Push(WillPush);
            }
            else if (GraphArr[I].ToPos == "キッチナー") {
                WillPush.GenzaiPos = GraphArr[I].FromPos;
                WillPush.Path = "キッチナー" + "," + GraphArr[I].FromPos;
                WillPush.SumKyori = GraphArr[I].Kyori;
                stk.Push(WillPush);
            }
        }


        while (stk.Count > 0) {
            JyoutaiDef WorkJyoutai = stk.Pop();

            if (WorkJyoutai.GenzaiPos == "ペンブローク") {
                AnswerList.Add(WorkJyoutai);
                continue;
            }

            WillPush.Level = WorkJyoutai.Level + 1;

            for (int I = 0; I <= GraphArr.GetUpperBound(0); I++) {
                if (GraphArr[I].FromPos == WorkJyoutai.GenzaiPos) {
                    if (("," + WorkJyoutai.Path + ",").Contains("," + GraphArr[I].ToPos + ","))
                        continue;
                    WillPush.GenzaiPos = GraphArr[I].ToPos;
                    WillPush.Path = WorkJyoutai.Path + "," + GraphArr[I].ToPos;
                    WillPush.SumKyori = WorkJyoutai.SumKyori + GraphArr[I].Kyori;
                    stk.Push(WillPush);
                }
                else if (GraphArr[I].ToPos == WorkJyoutai.GenzaiPos) {
                    if (("," + WorkJyoutai.Path + ",").Contains("," + GraphArr[I].FromPos + ","))
                        continue;
                    WillPush.GenzaiPos = GraphArr[I].FromPos;
                    WillPush.Path = WorkJyoutai.Path + "," + GraphArr[I].FromPos;
                    WillPush.SumKyori = WorkJyoutai.SumKyori + GraphArr[I].Kyori;
                    stk.Push(WillPush);
                }
            }
        }

        int answerCnt = 0;
        foreach (JyoutaiDef each in AnswerList.OrderBy(X => X.SumKyori).ThenBy(X=>X.Path)) {
            Console.WriteLine("answer{0} 距離は{1} 経路は{2}",++answerCnt, each.SumKyori, each.Path);
        }
    }
}

実行結果

answer1 距離は525 経路はキッチナー,トロント,ベルビル,ペンブローク
answer2 距離は525 経路はキッチナー,バリー,ハンツビル,ペンブローク
answer3 距離は565 経路はキッチナー,トロント,バリー,ハンツビル,ペンブローク
answer4 距離は630 経路はキッチナー,バリー,ハンツビル,ノースベイ,ペンブローク
answer5 距離は665 経路はキッチナー,バリー,トロント,ベルビル,ペンブローク
answer6 距離は670 経路はキッチナー,トロント,バリー,ハンツビル,ノースベイ,ペンブローク
answer7 距離は675 経路はキッチナー,トロント,ベルビル,オタワ,ペンブローク
answer8 距離は815 経路はキッチナー,バリー,トロント,ベルビル,オタワ,ペンブローク

解説

経路を列挙してからLINQのOrderBy拡張メソッドでソートしてます。