플로이드 와샬 알고리즘

백준 문제를 풀면서 플로이드 와샬 알고리즘에 대해 궁금증이 생겨서 적어둔다!

 

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

• 그래프에서 모든 정점 간의 최단 경로를 찾는 알고리즘. 음의 가중치를 가지는 그래프에서도 동작하며, 그래프의 모든 정점 쌍 간의 최단 경로를 구하는데 사용된다. 다이나믹 프로그래밍 기법(DP)를 활용하여 문제를 효율적으로 해결한다.
• 기본 아이디어는 "거쳐가는 정점"을 기준으로 최단경로를 구하는 것이다.
• 동작 방식
  1.  초기화 : 그래프의 인접 행렬을 사용하여 최단 거리를 나타내는 2차원 배열을 초기화한다. 만약 두 정점 사이에 간선이 없으면 무한대(Infinity)로 설정.
  2. 중첩 반복문 : 모든 정점을 순회하여 해당 정점을 거쳐가는 경우를 고려한다.
  3. 최단 거리 갱신 : 현재 선택된 노드를 거쳐가는 경우와 그렇지 않은 경우를 비교하여 더 짧은 경로가 있다면 최단 거리 갱신.
  4. 모든 정점 순회 : 모든 정점을 순회하고 위의 과정을 반복.
• 시간 복잡도는 정점의 개수를 V 라고 할 때 O(V^3)이다. 정점의 개수가 많아질수록 실행 시간이 증가하므로 큰 그래프에는 적용하기 어렵지만 작은 규모의 그래프에는 효율적으로 동작한다.

 

플로이드 와샬 예시 코드 - Javascript

function floydWarshall(graph) {
  const V = graph.length; // 그래프의 정점 개수

  // 결과를 저장할 2차원 배열 초기화
  const dist = Array.from({ length: V }, () => Array.from({ length: V }, () => Infinity));

  // 자기 자신으로 가는 거리는 0으로 초기화
  for (let i = 0; i < V; i++) {
    dist[i][i] = 0;
  }

  // 그래프의 간선 정보로 dist 배열 초기화
  for (let i = 0; i < V; i++) {
    for (let j = 0; j < V; j++) {
      if (graph[i][j] !== 0) {
        dist[i][j] = graph[i][j];
      }
    }
  }

  // 중첩 반복문을 사용하여 거쳐가는 정점을 고려하여 최단 거리를 업데이트
  for (let k = 0; k < V; k++) {
    for (let i = 0; i < V; i++) {
      for (let j = 0; j < V; j++) {
        if (dist[i][k] !== Infinity && dist[k][j] !== Infinity && dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }

  return dist;
}

// 예시 그래프의 인접 행렬
const graph = [
  [0, 3, Infinity, 7],
  [8, 0, 2, Infinity],
  [5, Infinity, 0, 1],
  [2, Infinity, Infinity, 0],
];

const shortestDistances = floydWarshall(graph);
console.log(shortestDistances);

 

코드 설명

• 바깥쪽 반복문 ( k ) : 거쳐가는 정점을 선택하는 반복문. 처음에는 아무 정점도 거쳐가지 않은 상태로 시작하며, 이후 한 단계씩 거쳐가는 정점의 개수를 늘려가며 모든 정점을 순회.
• 중간쪽 반복문 ( i ) : 출발 정점을 선택하는 반복문. 거쳐가는 정점을 기준으로 출발 정점과 도착 정점 사이의 최단 거리르 계산.
• 안쪽 반복문 ( j ) : 도착 정점을 선택하는 반복문. 거쳐가는 정점을 기준으로 출발 정점과 도착 정점 사이의 최단 거리를 계산.
• 'k'번째 정점을 거쳐가는 경우를 고려하여 'i' 번째 정점에서 'j' 번째 정점으로의 최단 거리를 업데이트.
• 'dist[i][k]' 는 정점 'i'에서 정점 'k'를 거쳐가는 경우의 최단거리.
• 'dist[k][j]' 는 정점 'k'에서 정점 'j'를 거쳐가는 경우의 최단거리.
• 'dist[i][k] + dist[k][j]' 는 정점 'i'에서 정점 'j'를 거쳐가는 경로를 고려한 거리의 합.
• 'if'문은 현재까지 계산된 최단거리( 'dist[i][j]' )보다 'k'번째 정점을 거쳐가는 경로( 'dist[i][k] + dist[k][j]' )가 더 짧을 경우에만 최단 거리를 업데이트한다. 그래야 항상 최단 거리를 유지할 수 있다.