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

 

이번에는 최단거리 알고리즘의 마지막! 플로이드 와샬에 대해 알아보자. 

 

플로이드 와샬은 다른 최단거리 알고리즘 중에서 제일 느리다. 

 

왜냐하면 딕스트라나 벨만 포드는 모두 출발점이라는 개념이 있는데 플로이드 와샬은 그런 거 모르겠고

 

모든 노드의 최단거리를 다 구해 버리기 때문이다. 

 

자바스크립트 구현 코드

 

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];
            }
        }
    }
}

아마 처음 코드를 보면 어리둥절 할 것이다. 

 

하지만 원리를 보면 그렇게 어려운 개념은 아니다. 

 

기본적으로 i 는 거쳐가는 노드를 말한다.

 

1에서 4로 가는 경우를 생각해보자. 

 

1에서 바로 4로 가는 경우 초기 dist 그래프에 이미 그려져 있을 것이다. 

 

문제는 1에서 2를 통해 4로 갈 수 도 있고 1에서 3을 통해 4로도 갈 수 있다. 

 

위 코드는 2를 통해 갈 때 거리를 dist와 비교해 더 작다면 2를 통해 가는 거리를 입력하게 된다. 

 

그러고 나서 i는 순차적으로 증가해 1에서 3을 통해 가는 경우도 계산해 대입하게 된다.