[JS] 플로이드-워셜 알고리즘: 다익스트라 같은데 뭔가 안될때

얼마전에 다익스트라 알고리즘을 다뤘었죠

[JS] 등산코스 정하기 - 다익스트라 알고리즘에 대해서

 

이번엔 플로이드-워셜입니다.

기능은 역시 "최소 경로 찾기"에 이용됩니다.

다만, 다익스트라와의 차이점이라고 한다면, 모든 정점에서의 최소 거리를 구한다는 점입니다.

노드의 시작 지점이 계속 바뀌는 문제를 다룬다면, 플로이드-워셜 알고리즘을 쓰기 적합한 문제일 것 같습니다.

 

출처: https://school.programmers.co.kr/learn/courses/30/lessons/72413

 

전 이 문제를 풀다가 플로이드-워셜을 적용해야하는 걸 알았는데요.

예를 들어 모든 정점에서 갈 수 있는 최소 길이의 정점을 구해줘야합니다.

구하는 방법은 이런 식입니다.

 

시작 노드	중간 노드	도착 노드	비용	설명
1	1	3	41	노드 1에서 연결된 모든 노드를 탐색
1	1	5	24
1	1	6	25
2	1	3	INF	노드 2에서 노드 1을 거쳐 연결된 모든 노드를 탐색
2	1	4	INF

 

시작 노드가 있고 도착 노드가 있을 때 중간에 거치는 노드까지 계산을 해줍니다.

2에서 1을 거치는 경로가 없으니 무조건 INFINITY로 설정을 해줍시다.

 

그럼 코드를 한 번 살펴보죠!

const graph = [
    [0, Infinity, 41, 10, 24, 25],
    [Infinity, 0, 22, 66, Infinity, Infinity],
    [41, 22, 0, Infinity, 24, Infinity],
    [10, 66 , Infinity, 0, Infinity, 60],
    [24, Infinity, 24, Infinity, 2],
    [25, Infinity, Infinity, 50, 2, 0],
];

function floyd(graph) {
    const n = graph.length;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            for (let k = 0; k < n; k++) {
                if (graph[j][k] > graph[j][i] + graph[i][k]) {
                    graph[j][k] = graph[j][i] + graph[i][k];
                }
            }
        }
    }
}

 

index가 3개여서 구현할 때 헷갈릴 수 있는데요.

 

시작지점 > 중간지점 > 도착지점

 

이 순서를 잘 생각해보시면 저렇게 되는게 이해가 될 것 같습니다.

도착지점을 먼저 순회하고, 그 다음이 시작지점, 마지막으로 중간지점을 순회합니다.

 

그럼 다음 포스트에선 저 합승 택시 요금 문제를 한 번 다뤄보도록 하죠!