플로이드 와샬 알고리즘

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

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

  • &#8734; &#x221e; &infin; 236

윗첨자, 아랫첨자

  • <sup><sub>

후기

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

좋은 웹페이지 즐겨찾기