floydとshallアルゴリズム
9910 ワード
フロイドとシャールアルゴリズムとは何ですか?
上の図では、各頂点から別の頂点へのコストが2 D配列で表示されます.
1
2
3
4
1
0
5
∞
8
2
7
0
9
∞
3
2
∞
0
4
4
∞
∞
3
0
頂点1を通過
1
2
3
4
1
0
5
∞
8
2
7
0
更新
更新
3
2
更新
0
更新
4
∞
更新
更新
0
更新1を含まない部分と自分を含まない部分
これを2次元配列に置き換えると
1
2
3
4
1
0
5
∞
8
2
7
0
9
15
3
2
7
0
4
4
∞
∞
3
0
頂点2を通過
1
2
3
4
1
0
5
更新
更新
2
7
0
9
15
3
更新
7
0
更新
4
更新
∞
更新
0
1
2
3
4
1
0
5
14
8
2
7
0
9
15
3
2
7
0
4
4
∞
∞
3
0
頂点3を通過
1
2
3
4
1
0
更新
14
更新
2
更新
0
9
更新
3
2
7
0
4
4
更新
更新
3
0
1
2
3
4
1
0
5
14
8
2
7
0
9
13
3
2
7
0
4
4
5
10
3
0
頂点4を通過
1
2
3
4
1
0
更新
更新
8
2
更新
0
更新
13
3
更新
更新
0
4
4
5
10
3
0
1
2
3
4
1
0
5
11
8
2
7
0
9
13
3
2
7
0
4
4
5
10
3
0
初期2 Dアレイ
1
2
3
4
1
0
5
∞
8
2
7
0
9
∞
3
2
∞
0
4
4
∞
∞
3
0
最終アレイのステータス
1
2
3
4
1
0
5
11
8
2
7
0
9
13
3
2
7
0
4
4
5
10
3
0
ソースコード
let number = 4;
// 자료 배열 초기화
let a = [
[0,5,Infinity,8],
[7,0,9,Infinity],
[2,Infinity,0,4],
[Infinity,Infinity,3,0]
];
let floydWarshall = () => {
// 결과 그래프 초기화
let b = a.slice();
// 거쳐가는 Vertex
for(let k=0; k<number; k++) {
// 출발 vertex
for(let i=0; i<number; i++) {
// 거쳐가는 v와 출발하는 v 같으면 다음 인덱스로
if(k === i) continue;
// 도착 vertex
for(let j=0; j<number; j++ ) {
// 거쳐가는 v와 도착하는 v 같은 경우나
// 출발v와 도착v과 같은 경우 다음 인덱스
if(k === j || i === j) continue;
if(b[i][j] > b[i][k] + b[k][j]) {
b[i][j] = b[i][k] + b[k][j];
}
}
}
}
console.table(b);
}
ソース
[動賓座のfloydとshallアルゴリズム](blogyoutube)
Tip
htmlタグに無限タグを付ける
∞ ∞ ∞ 236 <sup><sub> ポスト
このアルゴリズムを習い始めたばかりの頃、これは何なのか頭の中で考えていました.
描けないので、動画やノートに何度も何度も何度も繰り返し描いて、やっと理解できました.難しいけど面白い!
Reference
この問題について(floydとshallアルゴリズム), 我々は、より多くの情報をここで見つけました https://velog.io/@dev_shu/플로이드-와샬-알고리즘テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol