어이 젊은이! 모든 최단경로 다 구해서 내앞으로 가져와
플.와를 들어가기에 앞서
- 제 블로그를 정독한 사람이라면, 앞서 배운 다익스트라 알고리즘을 통해서 특정 노드에서 부터 다른 노드까지의 최단 거리를 구할 수 있었습니다. 다익스트라의 시간 복잡도는
- 간선의 갯수를 E, 정점의 개수를 V라고 했을 때 **O(ElogV)**의 시간 복잡도를 갖습니다.
- 만약 우리가 다익스트라를 통해 모든 노드로부터 출발하는 최단 거리를 구했을 때는 O(V^2logV) 의 시간 복잡도를 갖게 됩니다.
- 이러한 지식을 바탕으로 플로이드 와샬에 대해서 알아보겠습니다.
플로이드 와샬 알고리즘이란?
- 플로이드 와샬 알고리즘은 정점 갯수가 V인 그래프에서 한 번에 모든 정점 사이의 최단 거리를 구해내는 알고리즘입니다.
- 이렇게 까지만 들으면, 다른 최단거리 알고리즘 필요없이 이것만 쓰면 되는 것이 아니냐? 할텐데,,, 방법에 대해 들어보면,,, 아닌걸 아실껍니다.
- 플로이드 와샬 알고리즘은 정점 a, b에 대해 a 에서 b로 가는 최단 경로를 한 번에 구해야 합니다. 따라서 다음과 같은 준비물이 필요합니다.
- 총 노드의 개수를 N 이라고 합시다.
- a정점에서 b정점으로의 거리를 나타낼 수 있는 N^2 크기의 2차 배열 board를 만듭니다.
- 대부분 자신에서 자신으로 가는 것은 cost가 0이므로
board[i][j] = 0 (if i == j)로 설정합니다. - 데이터를 받기 전까지 a에서 b로 가는 cost를 모르니, 나머지는
board[i][j] = INF값으로 나올 수 없는 최대값으로 설정을 해줍니다. - 이렇게 한다면 사전에 준비해야될 내용들은 끝인 겁니다.
- 대부분 자신에서 자신으로 가는 것은 cost가 0이므로
- 플로이드 최단경로를 DP 형태로 정의하고 해결하는 방식을 씁니다.
- a 에서 b까지 가는데 k라는 것을 지나칠 수 있다고 가정해봅시다. (k가 있을 수도, 없을 수도 있습니다)
- 그렇다면 a -> b의 거리와 a -> k -> b의 거리중에 작은 값을 갖고 있는 것이 최단 거리가 될 것입니다.
- 이러한 반복을 총 3개의 루프문을 통해서 확인을 해주면서 메모라이제이션을 해줄 것입니다.
if (board[a][b] > board[a][k] + board[k][b])라면 최소값을 바꿔줍니다.
- 총 3개의 루프문을 통해서 확인해주므로, O(N^3)의 시간복잡도를 갖게 되고, 위에서 언급한 모든 노드에 대한 다익스트라의 O(N^2 * logN) 의 시간 복잡도와 비교했을 때 N^2개의 노드 이하까지는 다익스트라가 유리한 것을 알 수 있습니다.
- 대부분 플로이드 와샬을 구하는 문제를 확인해보면 N 값이 백단위이기 때문에, 어떤것을 써도 상관이 없을 겁니다,,
- 코드를 봐보도록 할게요!