[JS] 플로이드 와샬 알고리즘

1. 플로이드 와샬 알고리즘

 지난 번에 포스팅했던 다익스트라 알고리즘은 하나의 정점을 출발점으로해서 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 그런데 이번에 포스팅할 플로이드 와샬 알고리즘은 모든 각각의 정점을 출발점으로해서 모든 정점까지의 최단경로를 구하는 알고리즘이다. 하나의 정점을 출발하는 것이 아니라, 그래프에 있는 모든 각각의 경로에 대한 최단경로를 구하기 때문에 시간복잡도는 O(N³)이다. 또한 플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 이게 무슨 말인지 감이 안오더라도, 지금부터 하는 설명을 들으면 어떤 순서로 알고리즘이 수행되는지 알 수 있을 것이다. 

 

 

 [그림 1]은 그래프의 각 정점에 대한 가중치를 순차자료구조로 변환한 것이다.

 

[그림 1] 그래프 G와 가중치 배열

 먼저 출발 정점을 A로 설정하고, 거쳐야할 정점을 A로 설정하겠다. A에 인접한 정점은 B, D이다. 따라서 현재 A의 경로는 다음과 같다.

 

 

A(시작 정점) -> A(중간 정점) -> B, 이동거리 5

A(시작 정점) -> A(중간 정점) -> D, 이동거리 8

 

 

 이번엔 출발 정점을 B로 설정하고, 거쳐야할 정점을 A로 설정하겠다. B에 인접한 정점은 A, C다. 따라서 현재 B의 경로는 다음과 같다.

 

 

B(시작 정점) -> A(중간 정점) -> A, 이동거리 7

B(시작 정점) -> A(중간 정점) -> C, 이동거리 INF

 

 

 여기서 B -> A - > C의 이동거리(무한)보다 B -> C의 이동거리(9)가 더 작으므로 값은 그대로 9가 된다. 

 

 

 이번엔 출발 정점을 C로 설정하고, 거쳐야할 정점을 A로 설정하겠다. C에 인접한 정점은 A, D다. 현재 C의 경로는 다음과 같다.

 

C(시작 정점) -> A(중간 정점) -> A, 이동거리 2

C(시작 정점) -> A(중간 정점) -> D, 이동거리 10

 

 

 여기서 C -> A -> D의 이동거리(10)보다 C -> D의 이동거리(4)가 더 작으므로, 값 변경은 없다.

 

 

 이번엔 출발 정점을 D로 설정하고, 거쳐야할 정점을 A로 설정하겠다. D에 인접한 정점은 C다. 현재 D의 경로는 다음과 같다.

 

 

D(시작 정점) -> A(중간 정점) -> C, 이동거리 INF

 

 

여기서 D -> A -> C의 이동거리(무한)보다 D -> C의 이동거리(3)이 더 작으므로, 값 변화는 없다. 이렇게 거쳐야할 정점이 D가 될 때까지 반복하면 된다. 그리고 만들어진 경로와 기존의 경로를 비교해서 둘 중에 더 작은 값으로 업데이트하는 조건을 만들어 주면 된다. 이 조건을 다음과 같은 조건식으로 나타낼 수 있다.

 

 

d[시작 정점][인접 정점] > d[시작 정점][거쳐야할 정점] + d[인접 정점][거쳐야할 정점]

 

 

이를 프로그래밍하면 다음과 같다.

 

const INF = Infinity;

const floydWarshall = function(dist){
  const len = dist.length;
  for(let i=0; i<len; i++){
    for(let j=0; j<len; j++){
      for(let k=0; k<len; k++){
        if(dist[j][k] > dist[j][i] + dist[i][k])
          dist[j][k] = dist[j][i] + dist[i][k];
      }
    }
  }
}

const main = (function(){
  const graph = [
    [0, 5, INF, 8],
    [7, 0, 9, INF],
    [2, INF, 0, 4],
    [INF, INF, 3, 0]
  ];

  floydWarshall(graph);
  
  for(let i=0; i<graph.length; i++)
    console.log(graph[i]);
}());

 

 

2. 참고 자료

안경잡이 개발자 - 24. 플로이드 와샬(Floyd Warshall) 알고리즘