JavaScriptで蟻本 グラフ　 最小全域木 プリム法

# 概要
アルゴリズムの学習記録を投稿します。
今回は蟻本・グラフ・最小全域木のプリム法についてです。


# 問題
```
全域木の最小コストを求めよ。

入力
graph1 = [
        [INF,1,INF,INF,INF,INF,INF],
        [1,INF,3,INF,7,INF,2],
        [INF,3,INF,5,1,INF,INF],
        [INF,INF,5,INF,8,INF,INF],
        [INF,7,1,8,INF,5,INF],
        [INF,INF,INF,INF,5,INF,10],
        [INF,2,INF,INF,INF,10,INF]
        ]

vertexCount =  5

出力
17
```
※問題文は本には書かれていないので　入力と出力は自分がわかりやすいように書きました。

# コード部分
```javascript
//
/**最小全域木　プリム法　蟻本　p100
 *
 * @param graph{Array} 無向グラフ　隣接行列
 * @param vertexCount{Number} 頂点の数
 * @return {Number} 最小コスト
 */
const  prim = (graph,vertexCount) =>{
    let INF = 1000;
    // 初期化
    let used = new Array(vertexCount).fill(false);
    let mincosts = new Array(vertexCount).fill(INF); //最短経路
    let res = 0;
    mincosts[0] = 0;
    let loopCount = 0;
    console.log(`loopCount|u|v|used|res|条件|結果`);
    console.log(`---------|-|-|----|---|----|---`);
    while(true){
        let v = -1;
        for(let u=0; u<vertexCount; u++){
            // 最小となる頂点を探す
            if(!used[u] && (v == -1 || mincosts[u] < mincosts[v])) {
                loopCount++;
                v = u;
                console.log(`${loopCount}|${u}|${v}|${used}|${res}|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>${!used[u]} and (${v} =1 )| ${mincosts[u]} < ${mincosts[v]}`);
            }
        }

        if(v == -1) break;
        used[v] = true;
        res += mincosts[v];

        for(let u = 0;u < vertexCount; u++){
            loopCount++;
            mincosts[u] = Math.min(mincosts[u], graph[v][u]);
            console.log(`${loopCount}|${u}|${v}|${used}|${res}|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>${mincosts[u]}  = Math.min(${mincosts[v]},${graph[v][u]})`);
        }
    }
    return res;
}

let INF = 1000;
let graph1 = [[INF,1,INF,INF,INF,INF,INF],
        [1,INF,3,INF,7,INF,2],
        [INF,3,INF,5,1,INF,INF],
        [INF,INF,5,INF,8,INF,INF],
        [INF,7,1,8,INF,5,INF],
        [INF,INF,INF,INF,5,INF,10],
        [INF,2,INF,INF,INF,10,INF]
    ]

// 17
prim(graph1,7)


```

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

[Python Tutorリンク](https://pythontutor.com/render.html#code=//%0A/**%E6%9C%80%E5%B0%8F%E5%85%A8%E5%9F%9F%E6%9C%A8%E3%80%80%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95%E3%80%80%E8%9F%BB%E6%9C%AC%E3%80%80p100%0A%20*%0A%20*%20%40param%20graph%7BArray%7D%20%E7%84%A1%E5%90%91%E3%82%B0%E3%83%A9%E3%83%95%E3%80%80%E9%9A%A3%E6%8E%A5%E8%A1%8C%E5%88%97%0A%20*%20%40param%20vertexCount%7BNumber%7D%20%E9%A0%82%E7%82%B9%E3%81%AE%E6%95%B0%0A%20*%20%40return%20%7BNumber%7D%20%E6%9C%80%E5%B0%8F%E3%82%B3%E3%82%B9%E3%83%88%0A%20*/%0Aconst%20%20prim%20%3D%20%28graph,vertexCount%29%20%3D%3E%7B%0A%20%20%20%20let%20INF%20%3D%201000%3B%0A%20%20%20%20//%20%E5%88%9D%E6%9C%9F%E5%8C%96%0A%20%20%20%20let%20used%20%3D%20new%20Array%28vertexCount%29.fill%28false%29%3B%0A%20%20%20%20let%20mincosts%20%3D%20new%20Array%28vertexCount%29.fill%28INF%29%3B%20//%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%0A%20%20%20%20let%20res%20%3D%200%3B%0A%20%20%20%20mincosts%5B0%5D%20%3D%200%3B%0A%20%20%20%20let%20loopCount%20%3D%200%3B%0A%20%20%20%20console.log%28%60loopCount%7Cu%7Cv%7Cused%7Cres%7C%E6%9D%A1%E4%BB%B6%7C%E7%B5%90%E6%9E%9C%60%29%3B%0A%20%20%20%20console.log%28%60---------%7C-%7C-%7C----%7C---%7C----%7C---%60%29%3B%0A%20%20%20%20while%28true%29%7B%0A%20%20%20%20%20%20%20%20let%20v%20%3D%20-1%3B%0A%20%20%20%20%20%20%20%20for%28let%20u%3D0%3B%20u%3CvertexCount%3B%20u%2B%2B%29%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20//%20%E6%9C%80%E5%B0%8F%E3%81%A8%E3%81%AA%E3%82%8B%E9%A0%82%E7%82%B9%E3%82%92%E6%8E%A2%E3%81%99%0A%20%20%20%20%20%20%20%20%20%20%20%20if%28!used%5Bu%5D%20%26%26%20%28v%20%3D%3D%20-1%20%7C%7C%20mincosts%5Bu%5D%20%3C%20mincosts%5Bv%5D%29%29%20%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%20v%20%3D%20u%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20console.log%28%60%24%7BloopCount%7D%7C%24%7Bu%7D%7C%24%7Bv%7D%7C%24%7Bused%7D%7C%24%7Bres%7D%7C%E6%9C%80%E5%B0%8F%E3%81%A8%E3%81%AA%E3%82%8B%E9%A0%82%E7%82%B9%E3%82%92%E6%8E%A2%E3%81%99%20%3C/br%3E!used%5Bu%5D%20%26%26%20%28v%20%3D%3D%20-1%20or%20mincosts%5Bu%5D%20%3C%20mincosts%5Bv%5D%29%20%3C/br%3E%24%7B!used%5Bu%5D%7D%20and%20%28%24%7Bv%7D%20%3D1%20%29%7C%20%24%7Bmincosts%5Bu%5D%7D%20%3C%20%24%7Bmincosts%5Bv%5D%7D%60%29%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%0A%20%20%20%20%20%20%20%20if%28v%20%3D%3D%20-1%29%20break%3B%0A%20%20%20%20%20%20%20%20used%5Bv%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20res%20%2B%3D%20mincosts%5Bv%5D%3B%0A%0A%20%20%20%20%20%20%20%20for%28let%20u%20%3D%200%3Bu%20%3C%20vertexCount%3B%20u%2B%2B%29%7B%0A%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%20mincosts%5Bu%5D%20%3D%20Math.min%28mincosts%5Bu%5D,%20graph%5Bv%5D%5Bu%5D%29%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20console.log%28%60%24%7BloopCount%7D%7C%24%7Bu%7D%7C%24%7Bv%7D%7C%24%7Bused%7D%7C%24%7Bres%7D%7C%E6%9C%80%E5%B0%8F%E3%82%B3%E3%82%B9%E3%83%88%E3%82%92%E6%B1%82%E3%82%81%E3%82%8B%20%20%7C%20mincosts%5Bu%5D%20%3D%20Math.min%28mincosts%5Bu%5D,%20graph%5Bv%5D%5Bu%5D%29%3C/br%3E%24%7Bmincosts%5Bu%5D%7D%20%20%3D%20Math.min%28%24%7Bmincosts%5Bv%5D%7D,%24%7Bgraph%5Bv%5D%5Bu%5D%7D%29%60%29%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20return%20res%3B%0A%7D%0A%0Alet%20INF%20%3D%201000%3B%0Alet%20graph1%20%3D%20%5B%5BINF,1,INF,INF,INF,INF,INF%5D,%0A%20%20%20%20%20%20%20%20%5B1,INF,3,INF,7,INF,2%5D,%0A%20%20%20%20%20%20%20%20%5BINF,3,INF,5,1,INF,INF%5D,%0A%20%20%20%20%20%20%20%20%5BINF,INF,5,INF,8,INF,INF%5D,%0A%20%20%20%20%20%20%20%20%5BINF,7,1,8,INF,5,INF%5D,%0A%20%20%20%20%20%20%20%20%5BINF,INF,INF,INF,5,INF,10%5D,%0A%20%20%20%20%20%20%20%20%5BINF,2,INF,INF,INF,10,INF%5D%0A%20%20%20%20%5D%0A%20%20%20%20%0A//%2017%0Aprim%28graph1,7%29&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=js&rawInputLstJSON=%5B%5D&textReferences=false)

# その他情報

## 感想
問題文がないからそれがちょっと手間だったんだよなぁ…
入力値を考えるのに時間かかった



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


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710623/82da689c-e88d-f75d-a9ab-8202303f2466.png)


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

### 蟻本の値
loopCount|u|v|used|res|条件|結果
---------|-|-|----|---|----|---
1|0|0|false,false,false,false,false,false,false|0|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (0 =1 )| 0 < 0
2|0|0|true,false,false,false,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(0,1000)
3|1|0|true,false,false,false,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(0,1)
4|2|0|true,false,false,false,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1000  = Math.min(0,1000)
5|3|0|true,false,false,false,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1000  = Math.min(0,1000)
6|4|0|true,false,false,false,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1000  = Math.min(0,1000)
7|5|0|true,false,false,false,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1000  = Math.min(0,1000)
8|6|0|true,false,false,false,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1000  = Math.min(0,1000)
9|1|1|true,false,false,false,false,false,false|0|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (1 =1 )| 1 < 1
10|0|1|true,true,false,false,false,false,false|1|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(1,1)
11|1|1|true,true,false,false,false,false,false|1|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(1,1000)
12|2|1|true,true,false,false,false,false,false|1|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>3  = Math.min(1,3)
13|3|1|true,true,false,false,false,false,false|1|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1000  = Math.min(1,1000)
14|4|1|true,true,false,false,false,false,false|1|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>7  = Math.min(1,7)
15|5|1|true,true,false,false,false,false,false|1|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1000  = Math.min(1,1000)
16|6|1|true,true,false,false,false,false,false|1|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>2  = Math.min(1,2)
17|2|2|true,true,false,false,false,false,false|1|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (2 =1 )| 3 < 3
18|6|6|true,true,false,false,false,false,false|1|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (6 =1 )| 2 < 2
19|0|6|true,true,false,false,false,false,true|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(2,1000)
20|1|6|true,true,false,false,false,false,true|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(2,2)
21|2|6|true,true,false,false,false,false,true|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>3  = Math.min(2,1000)
22|3|6|true,true,false,false,false,false,true|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1000  = Math.min(2,1000)
23|4|6|true,true,false,false,false,false,true|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>7  = Math.min(2,1000)
24|5|6|true,true,false,false,false,false,true|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>10  = Math.min(2,10)
25|6|6|true,true,false,false,false,false,true|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>2  = Math.min(2,1000)
26|2|2|true,true,false,false,false,false,true|3|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (2 =1 )| 3 < 3
27|0|2|true,true,true,false,false,false,true|6|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(3,1000)
28|1|2|true,true,true,false,false,false,true|6|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(3,3)
29|2|2|true,true,true,false,false,false,true|6|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>3  = Math.min(3,1000)
30|3|2|true,true,true,false,false,false,true|6|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>5  = Math.min(3,5)
31|4|2|true,true,true,false,false,false,true|6|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(3,1)
32|5|2|true,true,true,false,false,false,true|6|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>10  = Math.min(3,1000)
33|6|2|true,true,true,false,false,false,true|6|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>2  = Math.min(3,1000)
34|3|3|true,true,true,false,false,false,true|6|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (3 =1 )| 5 < 5
35|4|4|true,true,true,false,false,false,true|6|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (4 =1 )| 1 < 1
36|0|4|true,true,true,false,true,false,true|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(1,1000)
37|1|4|true,true,true,false,true,false,true|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(1,7)
38|2|4|true,true,true,false,true,false,true|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(1,1)
39|3|4|true,true,true,false,true,false,true|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>5  = Math.min(1,8)
40|4|4|true,true,true,false,true,false,true|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(1,1000)
41|5|4|true,true,true,false,true,false,true|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>5  = Math.min(1,5)
42|6|4|true,true,true,false,true,false,true|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>2  = Math.min(1,1000)
43|3|3|true,true,true,false,true,false,true|7|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (3 =1 )| 5 < 5
44|0|3|true,true,true,true,true,false,true|12|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(5,1000)
45|1|3|true,true,true,true,true,false,true|12|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(5,1000)
46|2|3|true,true,true,true,true,false,true|12|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(5,5)
47|3|3|true,true,true,true,true,false,true|12|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>5  = Math.min(5,1000)
48|4|3|true,true,true,true,true,false,true|12|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(5,8)
49|5|3|true,true,true,true,true,false,true|12|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>5  = Math.min(5,1000)
50|6|3|true,true,true,true,true,false,true|12|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>2  = Math.min(5,1000)
51|5|5|true,true,true,true,true,false,true|12|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (5 =1 )| 5 < 5
52|0|5|true,true,true,true,true,true,true|17|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(5,1000)
53|1|5|true,true,true,true,true,true,true|17|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(5,1000)
54|2|5|true,true,true,true,true,true,true|17|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(5,1000)
55|3|5|true,true,true,true,true,true,true|17|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>5  = Math.min(5,1000)
56|4|5|true,true,true,true,true,true,true|17|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(5,5)
57|5|5|true,true,true,true,true,true,true|17|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>5  = Math.min(5,1000)
58|6|5|true,true,true,true,true,true,true|17|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>2  = Math.min(5,10)


### その他例１ 頂点数４個

```
入力
graph1 = [
        [INF,2,8,20],
        [2,INF,1,4],
        [8,1,INF,10],
        [20,4,10,INF]
        ]

vertexCount =  4

出力
7
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710623/ad5b7796-a243-7cee-a757-942ce3707b53.png)



loopCount|u|v|used|res|条件|結果
---------|-|-|----|---|----|---
1|0|0|false,false,false,false|0|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (0 =1 )| 0 < 0
2|0|0|true,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(0,1000)
3|1|0|true,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>2  = Math.min(0,2)
4|2|0|true,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>8  = Math.min(0,8)
5|3|0|true,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>20  = Math.min(0,20)
6|1|1|true,false,false,false|0|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (1 =1 )| 2 < 2
7|0|1|true,true,false,false|2|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(2,2)
8|1|1|true,true,false,false|2|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>2  = Math.min(2,1000)
9|2|1|true,true,false,false|2|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(2,1)
10|3|1|true,true,false,false|2|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>4  = Math.min(2,4)
11|2|2|true,true,false,false|2|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (2 =1 )| 1 < 1
12|0|2|true,true,true,false|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(1,8)
13|1|2|true,true,true,false|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(1,1)
14|2|2|true,true,true,false|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(1,1000)
15|3|2|true,true,true,false|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>4  = Math.min(1,10)
16|3|3|true,true,true,false|3|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (3 =1 )| 4 < 4
17|0|3|true,true,true,true|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(4,20)
18|1|3|true,true,true,true|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(4,4)
19|2|3|true,true,true,true|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(4,10)
20|3|3|true,true,true,true|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>4  = Math.min(4,1000)



### その他例2　頂点数５個

```
入力
graph1 = [
            [INF,2,8,20,INF],
            [2,INF,1,4,INF],
            [8,1,INF,10,30],
            [20,4,10,INF,5],
            [INF,INF,30,5,INF]
        ]

vertexCount =  5

出力
12

```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2710623/bbfb1f6b-7237-da5c-daea-20ce84fc741a.png)



loopCount|u|v|used|res|条件|結果
---------|-|-|----|---|----|---
1|0|0|false,false,false,false,false|0|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (0 =1 )| 0 < 0
2|0|0|true,false,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(0,1000)
3|1|0|true,false,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>2  = Math.min(0,2)
4|2|0|true,false,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>8  = Math.min(0,8)
5|3|0|true,false,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>20  = Math.min(0,20)
6|4|0|true,false,false,false,false|0|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1000  = Math.min(0,1000)
7|1|1|true,false,false,false,false|0|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (1 =1 )| 2 < 2
8|0|1|true,true,false,false,false|2|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(2,2)
9|1|1|true,true,false,false,false|2|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>2  = Math.min(2,1000)
10|2|1|true,true,false,false,false|2|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(2,1)
11|3|1|true,true,false,false,false|2|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>4  = Math.min(2,4)
12|4|1|true,true,false,false,false|2|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1000  = Math.min(2,1000)
13|2|2|true,true,false,false,false|2|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (2 =1 )| 1 < 1
14|0|2|true,true,true,false,false|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(1,8)
15|1|2|true,true,true,false,false|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(1,1)
16|2|2|true,true,true,false,false|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(1,1000)
17|3|2|true,true,true,false,false|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>4  = Math.min(1,10)
18|4|2|true,true,true,false,false|3|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>30  = Math.min(1,30)
19|3|3|true,true,true,false,false|3|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (3 =1 )| 4 < 4
20|0|3|true,true,true,true,false|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(4,20)
21|1|3|true,true,true,true,false|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(4,4)
22|2|3|true,true,true,true,false|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(4,10)
23|3|3|true,true,true,true,false|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>4  = Math.min(4,1000)
24|4|3|true,true,true,true,false|7|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>5  = Math.min(4,5)
25|4|4|true,true,true,true,false|7|最小となる頂点を探す </br>!used[u] && (v == -1 or mincosts[u] < mincosts[v]) </br>true and (4 =1 )| 5 < 5
26|0|4|true,true,true,true,true|12|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>0  = Math.min(5,1000)
27|1|4|true,true,true,true,true|12|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(5,1000)
28|2|4|true,true,true,true,true|12|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>1  = Math.min(5,30)
29|3|4|true,true,true,true,true|12|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>4  = Math.min(5,5)
30|4|4|true,true,true,true,true|12|最小コストを求める  | mincosts[u] = Math.min(mincosts[u], graph[v][u])</br>5  = Math.min(5,1000)


# 参考資料

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

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

# githubコミット部分

https://github.com/RYA234/laravel9_vite_vue3/commit/2320dae76e6c0d1d25f3dc17606ea149108d5ec8