플로이드 와샬 알고리즘
플로이드 와샬 알고리즘이란?
- 다익스트라 알고리즘은 하나정의 정점에서 출발했을 때 다른 모든 정점으로의 최단경로를 구하는 알고리즘.
- 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 요 아록리즘을.
- 차이점
- 다익스트라 알고리즘은 가장 적은 Guarantee를 하나씩 선택함
- 거쳐가는 vertex를 기준으로 최단거리를 구하는 것
-
위의 그래프에서 각각의 vertex가 다른 vertex로 가는 비용을 2차원 배열형태로 보면
1 2 3 4 1 0 5 ∞ 8 2 7 0 9 ∞ 3 2 ∞ 0 4 4 ∞ ∞ 3 0 -
vertex 1을 거쳐가는 경우
1 2 3 4 1 0 5 ∞ 8 2 7 0 갱신 갱신 3 2 갱신 0 갱신 4 ∞ 갱신 갱신 0 -
1을 포함하지 않는 부분과 자기 자신을 제외한 부분을 갱신
- (2~1):7 + (1~3):∞ < (2~3):9 => (2~3):9
- (2~1):7 + (1~4):8 < (2~4):∞ => (2~4):15
- (3~1):2 + (1~2):5 < (3~2):∞ => (3~2):7
- (3~1):2 + (1~4):8 < (3~4):4 => (3~4):4
- (4~1):∞ + (1~2):5 < (4~2):∞ => (4~2):∞
- (4~1):∞ + (1~3):∞ < (4~3):3 => (4~3):3
-
이걸 2차원 배열로 바꾸면,
1 2 3 4 1 0 5 ∞ 8 2 7 0 9 15 3 2 7 0 4 4 ∞ ∞ 3 0 -
vertex 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
- 갱신 전
-
vertex 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
- 갱신 전
-
vertex 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차원 배열
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);
}
출처
Tip
html tag에선 무한대 표기하기
∞ ∞ ∞ 236
윗첨자, 아랫첨자
<sup><sub>
후기
맨처음 이 알고리즘을 공부했을 때, 이게 뭐지 하면서 머리 속에
그림이 안 그려져셔 동영상 및 노트에 그려가면서 여러 번 반복했더니 이해가 되었다. 어려웠지만 재밌었다!
Author And Source
이 문제에 관하여(플로이드 와샬 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dev_shu/플로이드-와샬-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)