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

프로그래머스 72413번 합승 택시 요금

 

해당 문제는 a와 b가 같은 출발지에서 출발하는데 서로의 목적지까지 얼마나 최소의 택시요금으로 갈 수 있는지 구하는 문제이다.

이는 결국 그래프의 최단 거리를 구하는 것이다.

 

그렇다면 그래프의 최단 거리를 구하는 알고리즘은 크게 3가지가 있다.

1. 다익스트라(Dijkstra)
2. 벨만 포드(Bellman-ford)
3. 플로이드 와샬(Floyd Wrashall)

이 중에서 해당 문제에 대해 적용하는 알고리즘은 플로이드 와샬 알고리즘이다. 

 

플로이드 와샬 (Folyd Warshall) 알고리즘

 

1.  어떠한 한 노드에서 특정 다른 노드까지의 최단 거리를 구하는 다익스트라 알고리즘, 벨만 포트 알고리즘과 달리

     플로이드 와샬은 모든 노드에 대한 최단 거리를 구한다. 

2. 음의 가중치가 있더라도 적용이 가능하지만, 음의 사이클이 존재할 경우에는 벨만 포드 알고리즘을 활용해야한다.

3. 최단 거리 정보를 저장할 때, 다른 알고리즘은 특정 노드에서의 최단 거리를 저장하기 때문에 1차월 배열을 사용하지만,

    플로이드 와샬은 모든 노드간의 최단 거리이기 때문에 2차원 배열을 사용한다.

 

 

점화식

D[i][j] = min(D[i][j], D[i][k] + D[k][j])

 

출발지 i부터 목적지 j까지 가는 최단 거리를 구할 때는 특정 노드 k를 거쳐가는 경우를 확인한 후, 바로 가는 것과 거쳐가는 것 중 어느 것이 최소 비용인지 확인 후에 테이블을 갱신해준다. 

 

 

 

과정을 알아보자!

1. 그래프 노드의 최단 거리 테이블을 작성한다.

 

도착 출발	1번	2번	3번	4번	5번	6번
1번	0	무한	41	10	무한	25
2번	0	0	22	66	무한	무한
3번	41	22	0	무한	24	무한
4번	10	66	무한	0	무한	50
5번	24	무한	24	무한	0	41
6번	25	무한	무한	50	41	0

 

 

 

2. 1번 노드를 거쳐가는 경우를 고려하여 테이블을 갱신한다.

1번 정점을 경유하는 상황이기 때문에 1번 노드에서 출발, 도착하는 경우는 제외하고 다른 노드들에 대해 둘러본다.

도착 출발	1번	2번	3번	4번	5번	6번
1번	0	무한	41	10	무한	25
2번	0	0	22	66	무한	무한
3번	41	22	0	51	24	66
4번	10	66	51	0	34	35
5번	24	무한	24	34	0	41
6번	25	무한	무한	35	41	0

 

 

 

 

3. 2번 노드를 거쳐가는 경우를 고려하여 테이블을 갱신한다.

도착 출발	1번	2번	3번	4번	5번	6번
1번	0	무한	41	10	무한	25
2번	0	0	22	66	무한	무한
3번	41	22	0	51	24	66
4번	10	66	51	0	34	35
5번	24	무한	24	34	0	41
6번	25	무한	무한	35	41	0

 

 

 

4. 3번 노드를 거쳐가는 경우를 고려하여 테이블을 갱신한다.

도착 출발	1번	2번	3번	4번	5번	6번
1번	0	63	41	10	무한	25
2번	0	0	22	66	46	무한
3번	41	22	0	51	24	66
4번	10	66	51	0	34	35
5번	24	46	24	34	0	41
6번	25	무한	무한	35	41	0

 

 

 

 

5. 4번 노드를 거쳐가는 경우를 고려하여 테이블을 갱신한다.

도착 출발	1번	2번	3번	4번	5번	6번
1번	0	63	41	10	무한	25
2번	0	0	22	66	46	116
3번	41	22	0	51	24	66
4번	10	66	51	0	34	35
5번	24	46	24	34	0	41
6번	25	116	무한	35	41	0

 

 

 

 

 

... 이런 식으로 6번 노드를 경우하는 상황까지 고려하여 테이블을 갱신해준다.

 

 

 

Javascript

// k: 경유 노드, i: 시작 노드, j: 도착 노드
for(let k=0; k<n; k++){
   for(let i=0; i<n; i++){
    	   for(let j=0; j<n; j++){
            node[i][j] = Math.min(node[i][k] + node[k][j], node[i][j]);
        }
    }
}

 

 

 

 

📚 참고자료

https://velog.io/@kimdukbae/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall-Algorithm