최단 경로 찾기 : 플로이드 워셜(Floyd-Warshall) 알고리즘

 

 

들어가며

 

오늘 살펴볼 알고리즘은 지난번에 살펴봤던 다익스트라 알고리즘과 마찬가지로 최단경로를 찾는 알고리즘 중 하나인 플로이드 워셜(Floyd-Warshall) 알고리즘입니다. 같은 목적을 가진 알고리즘이라 그런지 익숙하게 느껴지는데, 플로이드 워셜은 어떤 방법을 통해서 최단경로를 구하는지 살펴보도록 하겠습니다.

 

 

 

알고리즘

플로이드 워셜 알고리즘은 동적 계획법을 활용한 길찾기 알고리즘입니다. 다익스트라가 지금까지 방문한 지점에서 가장 짧은 거리에 있는 지점을 차례로 선택하여 길을 찾아가는 반면, 플로이드 워셜은 지점들 중 하나를 선택해 두 지점을 연결하는 경로 중 해당 지점을 경유하는 가장 짧은 거리를 갱신하여 저장하는 과정을 반복해 길을 찾아가는 방법입니다.

 

로직으로 만들기 쉽게 단계별로 살펴보면,

 

1. 경로 초기화
   • 정점과 연결된 간선들을 바탕으로 거리 정보를 담은 행렬을 구성합니다.
   • 연결되지 않은 정점의 거리는 무한대(Infinity)로 표시합니다.
2. 중간 지점을 기준으로 탐색
   • 해당 정점을 경유하는 최단 거리를 구하여 거리 행렬을 갱신합니다.
   • 이 과정을 모든 정점에서 반복합니다.

 

나뉘어진 단계를 보면, 모든 경우에 대한 순회를 진행한다는 것을 알 수 있습니다. 마치 버블 소트와도 비슷한 느낌입니다. 이해를 돕기 위해, 플로이드 워셜이 진행되는 과정을 간략한 그림으로도 살펴보겠습니다.

 

 

첫 번째 단계 : 초기화

 

첫 번째 단계는 초기화 단계입니다. 주어진 정보를 토대로 초기 거리 행렬(dist)을 구성해줍니다.

 

같은 지점끼리는 거리가 0이므로 0을, 경로가 존재하는 정점끼리는 해당하는 가중치를, 경로가 존재하지 않는 정점끼리는 무한대(INF)를 넣어줍니다. 이렇게 초기 상태를 만든 뒤, 알고리즘을 적용해보겠습니다.

 

 

 

두 번째 단계 : 1번 지점 경유

 

 

이제 중간 지점을 놓고, 경로를 갱신해 줄 차례입니다. 가장 먼저 1번 지점을 중간값으로 갖는 경로를 갱신해보겠습니다.

 

시작점과 끝점이 현재 선택한 중간 지점일 경우에는 경로의 최솟값이 변하지 않습니다. 따라서 [1번과 1번] , 또는 [1번과 2번] 경로는 값을 그대로 유지합니다.

 

그러나 2번과 3번처럼 경로에 현재 선택한 중간 지점이 포함된다면 거리 행렬이 갱신될 수 있습니다. 위 그래프에서 보면 2번에서 3번으로 곧장 가는 경로가 존재하지 않아 거리가 무한대(INF)로 표기되었지만, 2번과 3번 지점 모두 1번으로 갈 수 있기 때문에 경로가 새롭게 갱신됩니다.

 

• 2번 -> 1번 경로의 길이 : 3
• 3번 -> 1번 경로의 길이 : 2

 

이렇게 찾은 거리 값은 원래 행렬의 거리 값과 비교하여 더 작은 값을 행렬에 남깁니다. 기존 행렬의 값이 무한대(INF)였으니 더 작은 5가 행렬의 새로운 값이 됩니다.

 

 

세 번째 단계 : 2번 지점 경유

 

다음은 2번 지점을 중간 지점으로 가지는 경로를 찾습니다.

 

2번 지점을 경유하는 경로에서는 [1번과 2번], [2번과 5번] 을 통해 [1번과 5번] 의 경로를 구할 수 있습니다. 위와 같은 방법으로 갱신해줍니다.

 

 

• 1번 -> 2번 경로의 길이 : 3
• 5번 -> 2번 경로의 길이 : 6
• 갱신된 1번 -> 5번 경로의 길이 : 9

 

또한 1번 지점을 경유하며 갱신된 [2번과 3번] 의 경로를 이용하여 [3번과 5번] 의 경로도 구할 수 있습니다.

 

 

• 3번 -> 2번 경로의 길이 : 5
• 5번 -> 2번 경로의 길이 : 6
• 갱신된 3번 -> 5번 경로의 길이 : 11

 

 

네 번째 단계 : 3번 지점 경유

 

다음은 3번 지점입니다.

 

3번 지점을 경유하며 갱신되는 경로는 [1번과 4번], [2번과 4번] 경로입니다. 이외에는 경유하는 경로는 존재하나, 기존 경로보다 큰 값을 가지기에 거리 행렬이 갱신되지 않습니다.

 

 

• 1번 -> 3번 경로의 길이 : 2
• 4번 -> 3번 경로의 길이 : 1
• 갱신된 1번 -> 4번 경로의 길이 : 3

 

• 2번 -> 3번 경로의 길이 : 5
• 4번 -> 3번 경로의 길이 : 1
• 갱신된 2번 -> 4번 경로의 길이 : 6

 

다섯 번째 단계 : 4번 지점 경유

 

 

다음은 4번 지점입니다.

 

4번 지점을 지나며 갱신되는 경로는 [3번과 5번], [1번과 5번] 경로입니다. 이전에 갱신된 값들로 인해 더 짧은 경로를 찾을 수 있게 되었습니다.

 

• 3번 -> 4번 경로의 길이 : 1
• 5번 -> 4번 경로의 길이 : 4
• 갱신된 3번 -> 5번 경로의 길이 : 5

• 1번 -> 4번 경로의 길이 : 3
• 5번 -> 4번 경로의 길이 : 4
• 갱신된 1번 -> 5번 경로의 길이 : 7

 

 

여섯 번째 단계 : 5번 지점 경유

 

 

마지막으로 5번 지점입니다. 5번 지점을 중간 지점으로 갖는 경로들중, 기존 거리 행렬의 최솟값을 갱신할 새로운 경로는 없습니다. 따라서 행렬이 더 이상 갱신되지 않고, 이렇게 플로이드 워셜 알고리즘의 적용이 끝납니다.

 

 

 

구현

아래는 자바스크립트를 이용해 플로이드 워셜을 구현한 예시입니다.

 

function FloydWarshall(graph) {
  const INF = Infinity;
  const n = graph.length;
  const dist = [];

  for (let i = 0; i < n; i++) {
    dist[i] = [];
    for (let j = 0; j < n; j++) {
      if (i === j) {
        dist[i][j] = 0;
      } else if (graph[i][j] === 0) {
        dist[i][j] = INF;
      } else {
        dist[i][j] = graph[i][j];
      }
    }
  }

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] !== INF && dist[k][j] !== INF && dist[i][j] > dist[i][k] + dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }

  return dist;
}

 

 

알고리즘 특성상 3중첩 for문이 들어가기 때문에, 플로이드 워셜 알고리즘의 시간복잡도는 정점의 수가 N일때 O(N^3) 입니다. 다른 그래프 탐색 알고리즘에 비해 굉장히 느린 속도라고 볼 수 있겠습니다. 따라서 정점의 수가 많을 경우 다익스트라 알고리즘과 같은 다른 알고리즘을 사용하는 것이 바람직합니다.

 

 

 

마치며

이번 시간에는 플로이드 워셜 알고리즘의 특징과 적용 과정, 구현에 대해 알아보았습니다. 그러나 다익스트라와 플로이드 워셜 모두 음수 경로가 존재하는 그래프에서는 사용하기 어렵다는 공통점이 있습니다. 다음 시간에는 음수 간선이 존재하는 그래프에서도 사용할 수 있는 벨만-포드 알고리즘에 대해 알아보겠습니다.

 

긴 글 읽어주셔서 감사드리며, 잘못된 내용에 대한 지적은 언제든 댓글에 남겨주시기 바랍니다.