다이스트라(Dijkstra) : 하나의 점에서 출발했을 때 다른 모든 정점으로의 최단 경로(최소비용)를 구하는 알고리즘.
플로이드 와샬 : 모든 정점에서 모든 정점으로의 최단 경로(최소비용)를 구하고 싶을 때 사용한다.
거쳐가는 정점을 기준으로 최단 거리를 구하는 것
문제를 직접 풀어보며 알아보자.
N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때, 모든 도시에서 모든 도시로 이동하는데 쓰이는 비용의 최소값을 구하라.
✔️ 입력
- n : 도시의 수 (N<=100)
- edges : M개의 간선 정보 (M<=200)✔️출력
모든 도시에서 모든 도시로 이동하는데 드는 최소 비용을 아래와 같이 반환한다.
자기 자신으로 가는 비용은 0이고, i정점에서 j정점으로 갈 수 없을 때는 M이다.📌 입력1
5, [[1, 2, 6], [1, 3, 3], [3, 2, 2], [2, 4, 1], [2, 5, 13], [3, 4, 5], [4, 2, 3], [4, 5, 7]]📌 반환값1
[[0, 5, 3, 6, 13],
[M, 0, M, 1, 8],
[M, 2, 0, 3, 10],
[M, 3, M, 0, 7],
[M, M, M, M, 0]]
입력1에 edges를 그래프로 표현하면 다음과 같다.
이 때 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열의 형태로 출력하면 아래와 같다.
| dist | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 무한 | 무한 |
| 2 | 무한 | 0 | 무한 | 1 | 13 |
| 3 | 무한 | 2 | 0 | 5 | 무한 |
| 4 | 무한 | 3 | 무한 | 0 | 7 |
| 5 | 무한 | 무한 | 무한 | 무한 | 0 |
자기 자신으로 가는 것은 비용이 0, 정점에서 갈 수 없는 곳은 무한으로 표시했다.
이 배열에 저장된 값은 현재까지 계산한 최소 비용이다. 최소 비용 계산을 반복해서, 최종적으로 모든 최소 비용을 구해야 한다.
이 때, 거쳐가는 정점을 반복해서 바꾸며 기준으로 최소 비용을 계산하면된다.
정점 i에서 정점 j로 가는 경로 사이에, 정점 k를 들려서 방문하게 되는 경우를 고려해 최소 비용을 계산한다.
이 경우 k에 들어가는 1~n가지 모든 경우는 항상 i에서 k정점까지의 최소 비용을 이미 계산해 놓은 값이라서,
i와 k정점 사이에 또 다른 정점을 들리는 경우는 따로 고려해주지 않아도 된다.
예를 들어보면, 위의 그래프에서 정점 1에서 정점 5까지 가는 경우를 생각해보자.
이 경우, 정점 1에서 3을 거치고 최종적으로 4를 거쳐, 정점 5에 도착하게 된다.
이때 최소비용을 저장해놓은 배열에는 정점 1에서부터 정점 4까지의 최소비용을 저장해 두었으므로,
정점 1 => 정점 4 => 정점 5 일 때 최소비용을 고려하면 자동으로 정점 3을 거치게 된다는 것이다.
이를 javascript 코드로 구현하면 다음과 같다.
function solution(n, edges) {
let answer = 0;
let dist = Array.from(Array(n + 1), () => Array(n + 1).fill(1000));
for (let i = 0; i <= n; i++) dist[i][i] = 0;
for (let [a, b, c] of edges) {
dist[a][b] = c;
}
for (let k = 1; k <= n; k++) {
// 중간정점
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
// 기존 값보다 작으면 교체!!
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
return dist;
}