다익스트라(Dijkstra) 알고리즘은 하나의 시작 노드에서 다른 모든 노드까지의 최단 거리와 경로를 구하는 데 사용됩니다. 하지만 경우에 따라서는 모든 노드에서 다른 모든 노드까지의 최단 경로를 한 번에 구해야 할 필요가 있습니다. 이럴 때 유용한 것이 바로 '전체 쌍 최단 경로(All Pairs Shortest Path)' 알고리즘이며, 그중 가장 널리 사용되는 것이 플로이드-워셜(Floyd-Warshall) 알고리즘입니다.
플로이드-워셜 알고리즘의 동작 원리
- N x N 크기의 거리 행렬을 생성하고 모든 값을 무한대(Infinity)로 초기화합니다.
- 각 간선(u, v)에 대해 해당 행렬의 값을 간선의 가중치로 업데이트하고, 자기 자신을 향하는 간선(v, v)의 가중치는 0으로 설정합니다.
- i, j, k 세 개의 반복자를 사용해 3중 중첩 루프를 실행합니다. 모든 노드 i에서 모든 노드 j까지의 거리를 계산할 때, k를 중간 경유지로 고려하여 기존 arr[i][j]보다 더 짧은 경로가 발견되면 거리를 갱신합니다.
여기서는 행렬 대신 객체(object)를 사용합니다. 복잡한 객체로 각 노드를 표현하는 경우에는 인덱스를 따로 추적할 필요가 없기 때문입니다.
그럼 실제 구현 코드를 살펴보겠습니다.
구현 예제
floydWarshallAlgorithm() {
let dist = {};
for (let i = 0; i < this.nodes.length; i++) {
dist[this.nodes[i]] = {};
// 이미 존재하는 간선에는 가중치를 그대로 할당
this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));
this.nodes.forEach(n => {
// 나머지 노드는 무한대로 설정
if (dist[this.nodes[i]][n] == undefined)
dist[this.nodes[i]][n] = Infinity;
// 자기 자신으로의 거리는 0으로 설정
if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
});
}
this.nodes.forEach(i => {
this.nodes.forEach(j => {
this.nodes.forEach(k => {
// i → k → j로 가는 경로가 i → j로 직접 가는 것보다
// 더 짧은지 확인하고, 그렇다면 새로운 값으로 갱신
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
});
});
});
return dist;
}
}아래 코드로 직접 테스트해볼 수 있습니다.
테스트 예제
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addEdge("A", "C", 100);
g.addEdge("A", "B", 3);
g.addEdge("A", "D", 4);
g.addEdge("D", "C", 3);
console.log(g.floydWarshallAlgorithm());출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
{
A: { C: 7, B: 3, D: 4, A: 0 },
B: { A: 3, B: 0, C: 10, D: 7 },
C: { A: 7, D: 3, B: 10, C: 0 },
D: { A: 4, C: 3, B: 7, D: 0 }
}시간 복잡도 참고
플로이드-워셜 알고리즘은 3중 중첩 루프를 사용하기 때문에 시간 복잡도는 O(N³)입니다. 이는 다익스트라 알고리즘을 모든 노드에 대해 반복 실행하는 것과 비슷하지만, 음수 가중치를 가진 간선이 있어도 올바르게 동작한다는 장점이 있습니다. 다만 그래프의 크기가 매우 클 경우 성능 저하가 발생할 수 있으므로, 노드 수가 적은 밀집 그래프(dense graph)에서 특히 유용하게 활용됩니다.