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]

```


# コード部分
```javascript
    //
    /** 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リンク](https://pythontutor.com/render.html#code=%20%20%20%20const%20%20bellmanford%20%3D%20%28start,vertexCount,edgeCount,edge,goal%29%20%3D%3E%7B%0A%0A%20%20%20%20%20%20%20%20const%20from%20%3D%200%3B%0A%20%20%20%20%20%20%20%20const%20to%20%3D%201%3B%0A%20%20%20%20%20%20%20%20const%20cost%20%3D2%3B%0A%20%20%20%20%20%20%20%20const%20INF%20%3D%201000000%3B%0A%20%20%20%20%20%20%20%20let%20minDistance%20%3D%20Array%28vertexCount%29.fill%28INF%29%3B%0A%20%20%20%20%20%20%20%20minDistance%5Bstart%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20let%20loopCount%20%3D%200%3B%0A%20%20%20%20%20%20%20%20console.log%28%60%E3%83%AB%E3%83%BC%E3%83%97%E6%95%B0%7Ci%7C%E8%BE%BA%E6%83%85%E5%A0%B1%5B%E5%A7%8B%E7%82%B9%E3%80%81%E7%B5%82%E7%82%B9%E3%80%81%E3%82%B3%E3%82%B9%E3%83%88%5D%7CisUpdated%7CminDistance%5Be%5Bfrom%5D%5D%20!%3D%20INF%20%20%3C/br%3E%26%26%20%28minDistance%5Be%5Bto%5D%5D%20%3E%20minDistance%5Be%5Bfrom%5D%5D%20%2B%20e%5Bcost%5D%29%7CminDistance%5Be%5Bto%5D%5D%E3%81%AE%E5%BC%8F%7CminDistance%5Be%5Bto%5D%5D%E3%81%AE%E5%80%A4%7CminDistance%E9%85%8D%E5%88%97%E3%81%AE%E5%80%A4%7C%60%29%0A%20%20%20%20%20%20%20%20console.log%28%60-------%7C-%7C------------------------%7C---------%7C------%7C-------%7C---%7C----%7C%60%29%0A%20%20%20%20%20%20%20%20while%28true%29%7B%0A%20%20%20%20%20%20%20%20%20%20%20let%20isUpdated%20%3D%20false%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20for%28let%20i%3D0%3B%20i%3C%20edgeCount%3B%20i%2B%2B%29%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20loopCount%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20let%20e%20%3D%20edge%5Bi%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20let%20temp%20%3D%20minDistance%5Be%5Bto%5D%5D%3B%20//%20console.log%E3%81%AB%E8%A1%A8%E7%A4%BA%E3%81%99%E3%82%8B%E7%94%A8%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%28minDistance%5Be%5Bfrom%5D%5D%20!%3D%20INF%20%26%26%20%28minDistance%5Be%5Bto%5D%5D%20%3E%20minDistance%5Be%5Bfrom%5D%5D%20%2B%20e%5Bcost%5D%29%29%20%7B%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20minDistance%5Be%5Bto%5D%5D%20%3D%20minDistance%5Be%5Bfrom%5D%5D%20%2B%20e%5Bcost%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20isUpdated%20%20%3D%20true%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20console.log%28%60%24%7BloopCount%7D%7C%24%7Bi%7D%7C%5B%24%7Be%7D%5D%7C%20%24%7BisUpdated%7D%7C%20%24%7BminDistance%5Be%5Bfrom%5D%5D%7D%20!%3D%20%24%7BINF%7D%20%3C/br%3E%20%24%7Btemp%7D%20%3E%20%24%7BminDistance%5Be%5Bfrom%5D%5D%7D%20%2B%20%24%7Be%5Bcost%5D%7D%20%3C/br%3E%20true%7CminDistance%5Be%5B%24%7Bfrom%7D%5D%28%20%3D%24%7Be%5Bcost%5D%7D%29%5D%20%2B%20e%5B%24%7Bcost%7D%5D%20%28%3D%20%24%7Be%5Bcost%5D%7D%29%3C/br%3E%20%24%7BminDistance%5Be%5Bfrom%5D%5D%7D%20%2B%20%24%7Be%5Bcost%5D%7D%7C%24%7BminDistance%5Be%5Bto%5D%5D%7D%20%7C%24%7BminDistance%7D%60%29%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7Delse%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20console.log%28%60%24%7BloopCount%7D%7C%24%7Bi%7D%7C%5B%24%7Be%7D%5D%7C%20%24%7BisUpdated%7D%7C%20%24%7BminDistance%5Be%5Bfrom%5D%5D%7D%20!%3D%20%24%7BINF%7D%20%3C/br%3E%20%24%7Btemp%7D%20%3E%20%24%7BminDistance%5Be%5Bfrom%5D%5D%7D%20%2B%20%24%7Be%5Bcost%5D%7D%20%3C/br%3E%20false%7C%E8%A8%88%E7%AE%97%E3%81%97%E3%81%AA%E3%81%84%7C%E8%A8%88%E7%AE%97%E3%81%97%E3%81%AA%E3%81%84%7C%24%7BminDistance%7D%60%29%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20if%28!isUpdated%29%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20console.log%28minDistance%29%3B%0A%0A%20%20%20%20%20%20%20%20return%20minDistance%5Bgoal%5D%3B%0A%20%20%20%20%7D%0A%20%20%20%20let%20edge%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%5B0,1,2%5D,%5B0,2,5%5D,%0A%20%20%20%20%20%20%20%20%5B1,2,4%5D,%5B1,3,6%5D,%5B1,4,10%5D,%5B1,0,2%5D,%0A%20%20%20%20%20%20%20%20%5B2,0,5%5D,%5B2,1,4%5D,%5B2,3,2%5D,%0A%20%20%20%20%20%20%20%20%5B3,2,2%5D,%5B3,1,6%5D,%5B3,5,1%5D,%0A%20%20%20%20%20%20%20%20%5B4,1,10%5D,%5B4,5,3%5D,%5B4,6,5%5D,%0A%20%20%20%20%20%20%20%20%5B5,3,1%5D,%5B5,4,3%5D,%5B5,6,9%5D,%0A%20%20%20%20%20%20%20%20%5B6,4,5%5D,%5B6,5,9%5D%0A%20%20%20%20%5D%3B%0A%20%20%20%20%0A%20%20%20%20//%20%E7%B5%90%E6%9E%9C%E5%80%A4%E3%81%AF16%0A%20%20%20%20console.log%28bellmanford%280,7,20,edge,6%29%29%3B&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=js&rawInputLstJSON=%5B%5D&textReferences=false)

# その他情報

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

```
正しい隣接リスト
    [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  </br>&& (minDistance[e[to]] > minDistance[e[from]] + e[cost])|minDistance[e[to]]の式|minDistance[e[to]]の値|minDistance配列の値|
-------|-|------------------------|---------|------|-------|---|----|
1|0|[0,1,2]| true| 0 != 1000000 </br> 1000000 > 0 + 2 </br> true|minDistance[e[0]( =2)] + e[2] (= 2)</br> 0 + 2|2 |0,2,1000000,1000000,1000000,1000000,1000000
2|1|[0,2,5]| true| 0 != 1000000 </br> 1000000 > 0 + 5 </br> true|minDistance[e[0]( =5)] + e[2] (= 5)</br> 0 + 5|5 |0,2,5,1000000,1000000,1000000,1000000
3|2|[1,2,4]| true| 2 != 1000000 </br> 5 > 2 + 4 </br> false|計算しない|計算しない|0,2,5,1000000,1000000,1000000,1000000
4|3|[1,3,6]| true| 2 != 1000000 </br> 1000000 > 2 + 6 </br> true|minDistance[e[0]( =6)] + e[2] (= 6)</br> 2 + 6|8 |0,2,5,8,1000000,1000000,1000000
5|4|[1,4,10]| true| 2 != 1000000 </br> 1000000 > 2 + 10 </br> true|minDistance[e[0]( =10)] + e[2] (= 10)</br> 2 + 10|12 |0,2,5,8,12,1000000,1000000
6|5|[1,0,2]| true| 2 != 1000000 </br> 0 > 2 + 2 </br> false|計算しない|計算しない|0,2,5,8,12,1000000,1000000
7|6|[2,0,5]| true| 5 != 1000000 </br> 0 > 5 + 5 </br> false|計算しない|計算しない|0,2,5,8,12,1000000,1000000
8|7|[2,1,4]| true| 5 != 1000000 </br> 2 > 5 + 4 </br> false|計算しない|計算しない|0,2,5,8,12,1000000,1000000
9|8|[2,3,2]| true| 5 != 1000000 </br> 8 > 5 + 2 </br> true|minDistance[e[0]( =2)] + e[2] (= 2)</br> 5 + 2|7 |0,2,5,7,12,1000000,1000000
10|9|[3,2,2]| true| 7 != 1000000 </br> 5 > 7 + 2 </br> false|計算しない|計算しない|0,2,5,7,12,1000000,1000000
11|10|[3,1,6]| true| 7 != 1000000 </br> 2 > 7 + 6 </br> false|計算しない|計算しない|0,2,5,7,12,1000000,1000000
12|11|[3,5,1]| true| 7 != 1000000 </br> 1000000 > 7 + 1 </br> true|minDistance[e[0]( =1)] + e[2] (= 1)</br> 7 + 1|8 |0,2,5,7,12,8,1000000
13|12|[4,1,10]| true| 12 != 1000000 </br> 2 > 12 + 10 </br> false|計算しない|計算しない|0,2,5,7,12,8,1000000
14|13|[4,5,3]| true| 12 != 1000000 </br> 8 > 12 + 3 </br> false|計算しない|計算しない|0,2,5,7,12,8,1000000
15|14|[4,6,5]| true| 12 != 1000000 </br> 1000000 > 12 + 5 </br> true|minDistance[e[0]( =5)] + e[2] (= 5)</br> 12 + 5|17 |0,2,5,7,12,8,17
16|15|[5,3,1]| true| 8 != 1000000 </br> 7 > 8 + 1 </br> false|計算しない|計算しない|0,2,5,7,12,8,17
17|16|[5,4,3]| true| 8 != 1000000 </br> 12 > 8 + 3 </br> true|minDistance[e[0]( =3)] + e[2] (= 3)</br> 8 + 3|11 |0,2,5,7,11,8,17
18|17|[5,6,9]| true| 8 != 1000000 </br> 17 > 8 + 9 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
19|18|[6,4,5]| true| 17 != 1000000 </br> 11 > 17 + 5 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
20|19|[6,5,9]| true| 17 != 1000000 </br> 8 > 17 + 9 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
21|0|[0,1,2]| false| 0 != 1000000 </br> 2 > 0 + 2 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
22|1|[0,2,5]| false| 0 != 1000000 </br> 5 > 0 + 5 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
23|2|[1,2,4]| false| 2 != 1000000 </br> 5 > 2 + 4 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
24|3|[1,3,6]| false| 2 != 1000000 </br> 7 > 2 + 6 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
25|4|[1,4,10]| false| 2 != 1000000 </br> 11 > 2 + 10 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
26|5|[1,0,2]| false| 2 != 1000000 </br> 0 > 2 + 2 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
27|6|[2,0,5]| false| 5 != 1000000 </br> 0 > 5 + 5 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
28|7|[2,1,4]| false| 5 != 1000000 </br> 2 > 5 + 4 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
29|8|[2,3,2]| false| 5 != 1000000 </br> 7 > 5 + 2 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
30|9|[3,2,2]| false| 7 != 1000000 </br> 5 > 7 + 2 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
31|10|[3,1,6]| false| 7 != 1000000 </br> 2 > 7 + 6 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
32|11|[3,5,1]| false| 7 != 1000000 </br> 8 > 7 + 1 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
33|12|[4,1,10]| false| 11 != 1000000 </br> 2 > 11 + 10 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
34|13|[4,5,3]| false| 11 != 1000000 </br> 8 > 11 + 3 </br> false|計算しない|計算しない|0,2,5,7,11,8,17
35|14|[4,6,5]| true| 11 != 1000000 </br> 17 > 11 + 5 </br> true|minDistance[e[0]( =5)] + e[2] (= 5)</br> 11 + 5|16 |0,2,5,7,11,8,16
36|15|[5,3,1]| true| 8 != 1000000 </br> 7 > 8 + 1 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
37|16|[5,4,3]| true| 8 != 1000000 </br> 11 > 8 + 3 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
38|17|[5,6,9]| true| 8 != 1000000 </br> 16 > 8 + 9 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
39|18|[6,4,5]| true| 16 != 1000000 </br> 11 > 16 + 5 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
40|19|[6,5,9]| true| 16 != 1000000 </br> 8 > 16 + 9 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
41|0|[0,1,2]| false| 0 != 1000000 </br> 2 > 0 + 2 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
42|1|[0,2,5]| false| 0 != 1000000 </br> 5 > 0 + 5 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
43|2|[1,2,4]| false| 2 != 1000000 </br> 5 > 2 + 4 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
44|3|[1,3,6]| false| 2 != 1000000 </br> 7 > 2 + 6 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
45|4|[1,4,10]| false| 2 != 1000000 </br> 11 > 2 + 10 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
46|5|[1,0,2]| false| 2 != 1000000 </br> 0 > 2 + 2 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
47|6|[2,0,5]| false| 5 != 1000000 </br> 0 > 5 + 5 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
48|7|[2,1,4]| false| 5 != 1000000 </br> 2 > 5 + 4 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
49|8|[2,3,2]| false| 5 != 1000000 </br> 7 > 5 + 2 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
50|9|[3,2,2]| false| 7 != 1000000 </br> 5 > 7 + 2 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
51|10|[3,1,6]| false| 7 != 1000000 </br> 2 > 7 + 6 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
52|11|[3,5,1]| false| 7 != 1000000 </br> 8 > 7 + 1 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
53|12|[4,1,10]| false| 11 != 1000000 </br> 2 > 11 + 10 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
54|13|[4,5,3]| false| 11 != 1000000 </br> 8 > 11 + 3 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
55|14|[4,6,5]| false| 11 != 1000000 </br> 16 > 11 + 5 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
56|15|[5,3,1]| false| 8 != 1000000 </br> 7 > 8 + 1 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
57|16|[5,4,3]| false| 8 != 1000000 </br> 11 > 8 + 3 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
58|17|[5,6,9]| false| 8 != 1000000 </br> 16 > 8 + 9 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
59|18|[6,4,5]| false| 16 != 1000000 </br> 11 > 16 + 5 </br> false|計算しない|計算しない|0,2,5,7,11,8,16
60|19|[6,5,9]| false| 16 != 1000000 </br> 8 > 16 + 9 </br> false|計算しない|計算しない|0,2,5,7,11,8,16



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

関数の引数部分
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710623/6c82ba4c-f9ee-885d-5eee-78456a3b0b35.png)


関数内のローカル変数部分
![image-1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710623/2d5f8841-f45c-23ba-23f7-363da66aec37.png)

# 参考資料

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

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

# githubコミット部分

https://github.com/RYA234/laravel9_vite_vue3/commit/4c5c73fbd874c7e1ba4fa6b465439f54583b97bb