플로이드 와샬 알고리즘

플로이드 와샬 알고리즘이란?

• 다익스트라 알고리즘은 하나정의 정점에서 출발했을 때 다른 모든 정점으로의 최단경로를 구하는 알고리즘.
• 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 요 아록리즘을.
• 차이점
  • 다익스트라 알고리즘은 가장 적은 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);
}

출처

[동빈좌의 플로이드 와샬 알고리즘] (blog, youtube)

Tip

html tag에선 무한대 표기하기

• ∞ ∞ ∞ 236

윗첨자, 아랫첨자

• <sup><sub>

후기

맨처음 이 알고리즘을 공부했을 때, 이게 뭐지 하면서 머리 속에
그림이 안 그려져셔 동영상 및 노트에 그려가면서 여러 번 반복했더니 이해가 되었다. 어려웠지만 재밌었다!