JavaScriptで蟻本 グラフ ベルマンフォード法

概要

アルゴリズムの学習記録を投稿します。
今回は蟻本・グラフのベルマンフォード法　p96についてです。

問題

以下隣接リストの点0-点7間の最短距離を求めなさい。

    [0,1,2],[0,2,5],
    [1,2,4],[1,3,6],[1,4,10],[1,0,2],
    [2,0,5],[2,1,4],[2,3,2],
    [3,2,2],[3,1,6],[3,5,1],
    [4,1,10],[4,5,3],[4,6,5],
    [5,3,1],[5,4,3],[5,6,9],
    [6,4,5],[6,5,9]

コード部分

    //
    /** p95 グラフ ベルマンフォード法
     * @param start{Number}  目的値の番号
     * @param vertexCount{Number}  頂点の数
     * @param edgeCount{Number}  辺の数
     * @param edge{Array}  隣接リスト 頂点数×頂点数の２次元配列  要素0:始点 要素1:終点 要素2:コスト
     * @param goal{Number}  目的値の番号
     * @return {Number} 最短経路のコスト
     */
    const  bellmanford = (start,vertexCount,edgeCount,edge,goal) =>{
        const from = 0;
        const to = 1;
        const cost =2;
        const INF = 1000000;
        let minDistance = Array(vertexCount).fill(INF);
        minDistance[start] = 0;
        let loopCount = 0;
        console.log(`ループ数|i|辺情報[始点、終点、コスト]|isUpdated|minDistance[e[from]] != INF  </br>&& (minDistance[e[to]] > minDistance[e[from]] + e[cost])|minDistance[e[to]]の式|minDistance[e[to]]の値|minDistance配列の値|`)
        console.log(`-------|-|------------------------|---------|------|-------|---|----|`)
        while(true){
           let isUpdated = false;
            for(let i=0; i< edgeCount; i++){
                loopCount++;
                let e = edge[i];
                let temp = minDistance[e[to]]; // console.logに表示する用
                if(minDistance[e[from]] != INF && (minDistance[e[to]] > minDistance[e[from]] + e[cost])) {

                    minDistance[e[to]] = minDistance[e[from]] + e[cost];
                    isUpdated  = true

                    console.log(`${loopCount}|${i}|[${e}]| ${isUpdated}| ${minDistance[e[from]]} != ${INF} </br> ${temp} > ${minDistance[e[from]]} + ${e[cost]} </br> true|minDistance[e[${from}]( =${e[cost]})] + e[${cost}] (= ${e[cost]})</br> ${minDistance[e[from]]} + ${e[cost]}|${minDistance[e[to]]} |${minDistance}`)
                }else{
                    console.log(`${loopCount}|${i}|[${e}]| ${isUpdated}| ${minDistance[e[from]]} != ${INF} </br> ${temp} > ${minDistance[e[from]]} + ${e[cost]} </br> false|計算しない|計算しない|${minDistance}`)
                }
            }
            if(!isUpdated) {
               break;}}
        console.log(minDistance);
        return minDistance[goal];
    }
    let edge = [
        [0,1,2],[0,2,5],
        [1,2,4],[1,3,6],[1,4,10],[1,0,2],
        [2,0,5],[2,1,4],[2,3,2],
        [3,2,2],[3,1,6],[3,5,1],
        [4,1,10],[4,5,3],[4,6,5],
        [5,3,1],[5,4,3],[5,6,9],
        [6,4,5],[6,5,9]
    ];
    // 結果値は16
    console.log(bellmanford(0,7,20,edge,6));

python tutor

コードを実際に動かせるwebサイト
ステップ実行かつステップ事の変数を確認できる特徴があります。
Python Tutorリンク

その他情報

感想

入力値に使うデータ構造を決定するのに時間が掛かりました。
隣接行列と隣接リストのうち隣接リストを採用したのですが、
正しい隣接リストがわからなく、色々施行錯誤していました。

正しい隣接リスト
    [0,1,2],[0,2,5],
    [1,2,4],[1,3,6],[1,4,10],[1,0,2],
    [2,0,5],[2,1,4],[2,3,2],
    [3,2,2],[3,1,6],[3,5,1],
    [4,1,10],[4,5,3],[4,6,5],
    [5,3,1],[5,4,3],[5,6,9],
    [6,4,5],[6,5,9]

誤って作成した隣接リスト
    [[0,1,2],[0,2,5],[1,2,4],[1,3,6],
    [1,4,10],[2,3,2],[3,5,1],[4,5,3],
    [4,6,5],[5,4,3],[5,6,9]]

状態遷移図

計算内容を明示する表。
ステップごとの変数の値を各列に表示します。
複雑な計算を行うコードを理解するのに役立つ表です。

ループ数	i	辺情報[始点、終点、コスト]	isUpdated	minDistance[e[from]] != INF && (minDistance[e[to]] > minDistance[e[from]] + e[cost])	minDistance[e[to]]の式	minDistance[e[to]]の値	minDistance配列の値
1	0	[0,1,2]	true	0 != 1000000 1000000 > 0 + 2 true	minDistance[e0] + e[2] (= 2) 0 + 2	2	0,2,1000000,1000000,1000000,1000000,1000000
2	1	[0,2,5]	true	0 != 1000000 1000000 > 0 + 5 true	minDistance[e0] + e[2] (= 5) 0 + 5	5	0,2,5,1000000,1000000,1000000,1000000
3	2	[1,2,4]	true	2 != 1000000 5 > 2 + 4 false	計算しない	計算しない	0,2,5,1000000,1000000,1000000,1000000
4	3	[1,3,6]	true	2 != 1000000 1000000 > 2 + 6 true	minDistance[e0] + e[2] (= 6) 2 + 6	8	0,2,5,8,1000000,1000000,1000000
5	4	[1,4,10]	true	2 != 1000000 1000000 > 2 + 10 true	minDistance[e0] + e[2] (= 10) 2 + 10	12	0,2,5,8,12,1000000,1000000
6	5	[1,0,2]	true	2 != 1000000 0 > 2 + 2 false	計算しない	計算しない	0,2,5,8,12,1000000,1000000
7	6	[2,0,5]	true	5 != 1000000 0 > 5 + 5 false	計算しない	計算しない	0,2,5,8,12,1000000,1000000
8	7	[2,1,4]	true	5 != 1000000 2 > 5 + 4 false	計算しない	計算しない	0,2,5,8,12,1000000,1000000
9	8	[2,3,2]	true	5 != 1000000 8 > 5 + 2 true	minDistance[e0] + e[2] (= 2) 5 + 2	7	0,2,5,7,12,1000000,1000000
10	9	[3,2,2]	true	7 != 1000000 5 > 7 + 2 false	計算しない	計算しない	0,2,5,7,12,1000000,1000000
11	10	[3,1,6]	true	7 != 1000000 2 > 7 + 6 false	計算しない	計算しない	0,2,5,7,12,1000000,1000000
12	11	[3,5,1]	true	7 != 1000000 1000000 > 7 + 1 true	minDistance[e0] + e[2] (= 1) 7 + 1	8	0,2,5,7,12,8,1000000
13	12	[4,1,10]	true	12 != 1000000 2 > 12 + 10 false	計算しない	計算しない	0,2,5,7,12,8,1000000
14	13	[4,5,3]	true	12 != 1000000 8 > 12 + 3 false	計算しない	計算しない	0,2,5,7,12,8,1000000
15	14	[4,6,5]	true	12 != 1000000 1000000 > 12 + 5 true	minDistance[e0] + e[2] (= 5) 12 + 5	17	0,2,5,7,12,8,17
16	15	[5,3,1]	true	8 != 1000000 7 > 8 + 1 false	計算しない	計算しない	0,2,5,7,12,8,17
17	16	[5,4,3]	true	8 != 1000000 12 > 8 + 3 true	minDistance[e0] + e[2] (= 3) 8 + 3	11	0,2,5,7,11,8,17
18	17	[5,6,9]	true	8 != 1000000 17 > 8 + 9 false	計算しない	計算しない	0,2,5,7,11,8,17
19	18	[6,4,5]	true	17 != 1000000 11 > 17 + 5 false	計算しない	計算しない	0,2,5,7,11,8,17
20	19	[6,5,9]	true	17 != 1000000 8 > 17 + 9 false	計算しない	計算しない	0,2,5,7,11,8,17
21	0	[0,1,2]	false	0 != 1000000 2 > 0 + 2 false	計算しない	計算しない	0,2,5,7,11,8,17
22	1	[0,2,5]	false	0 != 1000000 5 > 0 + 5 false	計算しない	計算しない	0,2,5,7,11,8,17
23	2	[1,2,4]	false	2 != 1000000 5 > 2 + 4 false	計算しない	計算しない	0,2,5,7,11,8,17
24	3	[1,3,6]	false	2 != 1000000 7 > 2 + 6 false	計算しない	計算しない	0,2,5,7,11,8,17
25	4	[1,4,10]	false	2 != 1000000 11 > 2 + 10 false	計算しない	計算しない	0,2,5,7,11,8,17
26	5	[1,0,2]	false	2 != 1000000 0 > 2 + 2 false	計算しない	計算しない	0,2,5,7,11,8,17
27	6	[2,0,5]	false	5 != 1000000 0 > 5 + 5 false	計算しない	計算しない	0,2,5,7,11,8,17
28	7	[2,1,4]	false	5 != 1000000 2 > 5 + 4 false	計算しない	計算しない	0,2,5,7,11,8,17
29	8	[2,3,2]	false	5 != 1000000 7 > 5 + 2 false	計算しない	計算しない	0,2,5,7,11,8,17
30	9	[3,2,2]	false	7 != 1000000 5 > 7 + 2 false	計算しない	計算しない	0,2,5,7,11,8,17
31	10	[3,1,6]	false	7 != 1000000 2 > 7 + 6 false	計算しない	計算しない	0,2,5,7,11,8,17
32	11	[3,5,1]	false	7 != 1000000 8 > 7 + 1 false	計算しない	計算しない	0,2,5,7,11,8,17
33	12	[4,1,10]	false	11 != 1000000 2 > 11 + 10 false	計算しない	計算しない	0,2,5,7,11,8,17
34	13	[4,5,3]	false	11 != 1000000 8 > 11 + 3 false	計算しない	計算しない	0,2,5,7,11,8,17
35	14	[4,6,5]	true	11 != 1000000 17 > 11 + 5 true	minDistance[e0] + e[2] (= 5) 11 + 5	16	0,2,5,7,11,8,16
36	15	[5,3,1]	true	8 != 1000000 7 > 8 + 1 false	計算しない	計算しない	0,2,5,7,11,8,16
37	16	[5,4,3]	true	8 != 1000000 11 > 8 + 3 false	計算しない	計算しない	0,2,5,7,11,8,16
38	17	[5,6,9]	true	8 != 1000000 16 > 8 + 9 false	計算しない	計算しない	0,2,5,7,11,8,16
39	18	[6,4,5]	true	16 != 1000000 11 > 16 + 5 false	計算しない	計算しない	0,2,5,7,11,8,16
40	19	[6,5,9]	true	16 != 1000000 8 > 16 + 9 false	計算しない	計算しない	0,2,5,7,11,8,16
41	0	[0,1,2]	false	0 != 1000000 2 > 0 + 2 false	計算しない	計算しない	0,2,5,7,11,8,16
42	1	[0,2,5]	false	0 != 1000000 5 > 0 + 5 false	計算しない	計算しない	0,2,5,7,11,8,16
43	2	[1,2,4]	false	2 != 1000000 5 > 2 + 4 false	計算しない	計算しない	0,2,5,7,11,8,16
44	3	[1,3,6]	false	2 != 1000000 7 > 2 + 6 false	計算しない	計算しない	0,2,5,7,11,8,16
45	4	[1,4,10]	false	2 != 1000000 11 > 2 + 10 false	計算しない	計算しない	0,2,5,7,11,8,16
46	5	[1,0,2]	false	2 != 1000000 0 > 2 + 2 false	計算しない	計算しない	0,2,5,7,11,8,16
47	6	[2,0,5]	false	5 != 1000000 0 > 5 + 5 false	計算しない	計算しない	0,2,5,7,11,8,16
48	7	[2,1,4]	false	5 != 1000000 2 > 5 + 4 false	計算しない	計算しない	0,2,5,7,11,8,16
49	8	[2,3,2]	false	5 != 1000000 7 > 5 + 2 false	計算しない	計算しない	0,2,5,7,11,8,16
50	9	[3,2,2]	false	7 != 1000000 5 > 7 + 2 false	計算しない	計算しない	0,2,5,7,11,8,16
51	10	[3,1,6]	false	7 != 1000000 2 > 7 + 6 false	計算しない	計算しない	0,2,5,7,11,8,16
52	11	[3,5,1]	false	7 != 1000000 8 > 7 + 1 false	計算しない	計算しない	0,2,5,7,11,8,16
53	12	[4,1,10]	false	11 != 1000000 2 > 11 + 10 false	計算しない	計算しない	0,2,5,7,11,8,16
54	13	[4,5,3]	false	11 != 1000000 8 > 11 + 3 false	計算しない	計算しない	0,2,5,7,11,8,16
55	14	[4,6,5]	false	11 != 1000000 16 > 11 + 5 false	計算しない	計算しない	0,2,5,7,11,8,16
56	15	[5,3,1]	false	8 != 1000000 7 > 8 + 1 false	計算しない	計算しない	0,2,5,7,11,8,16
57	16	[5,4,3]	false	8 != 1000000 11 > 8 + 3 false	計算しない	計算しない	0,2,5,7,11,8,16
58	17	[5,6,9]	false	8 != 1000000 16 > 8 + 9 false	計算しない	計算しない	0,2,5,7,11,8,16
59	18	[6,4,5]	false	16 != 1000000 11 > 16 + 5 false	計算しない	計算しない	0,2,5,7,11,8,16
60	19	[6,5,9]	false	16 != 1000000 8 > 16 + 9 false	計算しない	計算しない	0,2,5,7,11,8,16

依存関係グラフ

依存関係グラフは変数の結びつきを一目でわかりやすくするための図です。
変数の流れを確認しやすくすることでワーキングメモリの負担を減らすことができます。
作成方法はコード上の変数に丸付けて線を繋げています。

関数の引数部分

関数内のローカル変数部分

参考資料

プログラミングコンテストチャレンジブック [第2版]　マイナビ　p95

プログラマー脳　秀和システム
p73 python tutor
p71 状態遷移表　
p69 依存関係グラフ

githubコミット部分