플로이드 워셜 알고리즘 (with JavaScript)

# 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)

플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 필요로 할 때 사용한다.

특정 시작점에서 다른 지점까지의 최단 경로를 탐색하는 다익스트라 알고리즘보다 넓은 범위를 탐색하는 만큼 시간 복잡도는 O(N³)으로 매우 느리지만 구현이 매우 간편하다.

따라서 모수가 작으며 여러 지점 사이 거리를 파악해야 하는 상황에서 사용할 만 하다.

 

플로이드 워셜 알고리즘은 두 노드 사이 다른 노드를 거쳐 갔을 때 더 작은 비용이 발생하는지 확인하는 작업을 반복 수행한다.

Dynamic programming의 일종으로 볼 수 있으며 점화식으로 나타내면 다음과 같다.

$$ D_{ab}=min(D_{ab}, D_{ak} + D_{kb}) $$

이 과정에서 모든 경로를 전부 탐색하게 되며 이를 이차원 배열에 저장하게 된다.

 

# Process

1. 노드의 개수를 n이라 할 때, n x n 배열을 생성한다.
   • 이 때 배열의 (a, b) 요소는 a노드에서 b노드까지 경로의 비용이다.
   • 자기 자신끼리의 비용은 0이다.
2. 서로 연결된 노드는 간선의 비용으로 배열을 채우고 나머지는 무한으로 채운다.
3. 모든 노드에 대해 해당 노드를 거쳐가는 다른 경로 비용을 계산하여 더 작은 값으로 배열을 업데이트한다.

 

예시

아래 그래프는 오른쪽 배열과 같이 초기화할 수 있다.

0번 노드를 거쳐가는 경우를 모두 고려한다.

1번 노드를 거쳐가는 경우를 모두 고려한다.

2번 노드를 거쳐가는 경우를 모두 고려한다.

3번 노드를 거쳐가는 경우를 모두 고려한다.

 

# JavaScript로 구현

점화식을 3중 반복문 형태로 구현하면 된다.

function floydWarshall(graph) {
    const length = graph.length;
    for (let k = 0; k < length; k += 1) {
        for (let i = 0; i < length; i += 1) {
            for (let j = 0; j < length; j += 1) {
                let cost = graph[i][k] + graph[k][j];
                if (cost < graph[i][j]) {
                    graph[i][j] = cost;
                }
            }
        }
    }
    return graph;
}

예제를 실행해보면 다음과 같은 결과를 얻을 수 있다.

const INF = Number.MAX_SAFE_INTEGER;
const graph = [
    [0, 2, 1, 8],
    [3, 0, INF, INF],
    [INF, 5, 0, 4],
    [INF, 3, 3, 0]
];

console.log(floydWarshall(graph));
// [ [ 0, 2, 1, 5 ], [ 3, 0, 4, 8 ], [ 8, 5, 0, 4 ], [ 6, 3, 3, 0 ] ]