[Algorithm] 최단 경로 - 플로이드 - 워셜 알고리즘

PS + 알고리즘 공부했던 것 복습도 할 겸 써보는 알고리즘 설명(?)으로 첫 번째는 최단 경로 알고리즘 중 하나인 플로이드 - 워셜 알고리즘이다. 

 

최단 경로 문제는 그래프 상에서 두 정점 (노드) 사이의 최단 경로를 찾는 문제로 여러 알고리즘을 이용하여 해결할 수 있다. 플로이드 - 워셜, 다익스트라, 벨만 - 포드, A * 알고리즘 등으로 최단 경로 문제를 해결할 수 있다.

 

각 알고리즘의 특징은 다음과 같다.

플로이드 - 워셜	모든 정점들 사이의 최단 경로를 구할 수 있다. 3중 루프를 사용한다.
다익스트라	두 노드 사이의 최단 경로를 구할 수 있지만, 두 노드 사이의 가중치에 음수가 존재한다면 사용할 수 없다.
벨만 - 포드	다익스트라와 같이 두 노드 사이 최단 경로를 구할 수 있으며, 음수 가중치가 존재하는 경우에도 사용할 수 있다.
A *	휴리스틱 방법을 이용해 최단 경로 문제를 해결할 수 있다.

 

추가로 최단 경로 문제를 해결하기 위해 그래프를 코드 상으로 표현하는 방법을 알아보겠다.

1) 2차원 배열 사용하기, 2) 향하는 정점, 그 정점으로 갈 때의 가중치를 클래스로 구현하여 이용하는 방법이 있다.

1) 방법은 총 정점이 n개라면 n * n 행렬을 만들고, arr[i][j]에 i에서 j 정점으로 가는 가중치를 저장하는 방식이다. 물론 자신의 정점으로 향하는 경우에는 가중치가 0이므로 arr[i][i]에는 0이 저장된다. 

2) 방법은 클래스에 vertex, weight를 필드로 가지는 클래스를 만들고, 연결 리스트에 i 정점과 연결된 모든 노드들을 연결하는 방법으로 구현할 수 있다. 

 

이제 플로이드 - 워셜 방식에 대해 설명해 보겠다. (설명에 문제, 오류가 있다면 댓글로 남겨주세요..)

플로이드 - 워셜 방식은 그래프를 1) 방식인 2차원 배열을 이용하여 표현한다.

3개의 노드 (정점)

 

위 그래프에서 2번 정점에서 3번 정점으로 향하는 경우에 주목하자. 만약 1번 정점을 거치지 않고 바로 2 ~ 3으로 향한다면 소모 가중치는 5이다.

하지만 여기서 1번 정점을 거쳐서 3번 정점으로 이동한다면 그 가중치는 1 + 2 = 3으로 2 ~ 3으로 바로 이동하는 것 보다 더 작은 가중치로 이동할 수 있다.

이것이 플로이드 - 워셜 알고리즘의 핵심 개념을 예시로 표현한 것인데, i ~ j로 이동하는 경우에 1) 바로 i ~ j로 이동하기와 2) 연결 정점 k를 포함하여 i ~ k ~ j로 이동하는 경우의 가중치를 비교하는 것이다. 1)과 2)의 가중치를 비교해 더 작은 가중치로 이동하는 경우를 선택하여 arr[i][j]에 저장한다. 

 

이 원리를 모든 정점에 대해 반복하여 모든 정점들 사이에 최단 경로를 구할 수 있다. 앞서 설명에서 플로이드 - 워셜 알고리즘은 3중 반복문을 이용한다고 했는데 가장 바깥 반복문에 방문하고 지나갈 정점 k, 그 안의 반복문에 i, 가장 안쪽 반복문에 j 변수를 이용한다. 이제 모든 정점에 대해 반복하며 arr[i][j] (저장되어 있는 i ~ j 까지의 최단 경로)와 arr[i][k] + arr[k][j] (i에서 k, k에서 j로 이동하는 가중치)를 비교하여 더 작은 값을 arr[i][j]에 저장한다. 

arr[i][j]가 더 작다면 i에서 시작하여 k 정점을 거쳐서 j로 이동하는 것이 더 비효율적인 것을 의미하고, arr[i][k] + arr[k][j]가 더 작다면 i에서 k 정점을 거쳐 j로 이동하는게 더 최단 경로임을 의미한다.

 

이 과정을 모든 정점에 대해 반복하면 모든 정점들 사이의 최단 경로를 2차원 배열에 저장할 수 있다.

 

여담으로 필자는 이 알고리즘을 공부할 때 개념이 제대로 이해되지 않아 '정점 하나를 거쳐서 목적지로 가는게 더 유리한지 아닌지를 판정하는 것 같은데.. 만약에 2개 이상의 정점을 거쳐서 목적지로 가는 경우도 업데이트가 되는건가?' 라는 생각을 했었다.

결론만 말하면 위와 같은 생각은 할 필요가 없다.

예를 들어 1 ~ 3으로 이동하는데 1 ~ 2 ~ 3으로 이동하는게 더 유리하다면 이 경로를 이동했을 때의 최단 경로가 arr[1][3]에 저장될 것이다. 이제 1 ~ 5로 이동할 때, 1 ~ 5보다 1 ~ 3 ~ 5가 최단 경로라면 arr[1][3]에 저장된 최단 경로 값을 이용하여 1 ~ 5까지의 최단 경로를 구할 것이다. 즉, 앞서 구했던 1 ~ 2 ~ 3에서 2를 방문하여 최단 경로로 이동하는 것이 arr[1][3]에 저장되어 있으므로 위와 같은 걱정은 할 필요가 없다.

 

결론적으로 플로이드 - 워셜 알고리즘은 3중 루프를 이용해 모든 정점에 대해 한 정점을 중간에 방문하여 목적지로 이동하는 것이 더 유리한지, 방문하지 않고 출발지에서 목적지로 바로 이동하는 것이 유리한지 비교하며 최단 경로를 구하는 알고리즘이다. Boj에도 이 알고리즘을 연습할 수 있는 문제가 많이 있는데, 가장 기본적인 문제는 '11404: 플로이드'로 해당 문제의 풀이도 차후 업로드 예정이다.