그래프 3
특정 노드에서 특정 노드로 최소 비용 경로
전체 값이 작은 최소 비용 신장 트리 때와는 달리 특정 노드에서 특정 노드로 이동할때 최소 가중치를 이용한 path를 구축하고 싶을 수 있다. 이럴 때 사용하는 알고리즘은 아래와 같다.
다익스트라 알고리즘(Dijkstra algorithm)
동적 계획법 (Dynamic programming) 기법을 이용해서 구하는 방법으로 최단 경로는 여러개의 최단 경로로 연결되어있기 때문에 동적 계획법을 통해서 구할 수 있다.
동적 계획법을 쓰기 때문에 이전 데이터를 보관할 방법이 필요한데 1 차원 배열을 통해서 해당 데이터를 보관하면 된다. 이번 포스팅의 경우 배열의 이름 역시 중요하므로 2 차원 배열을 이용하여 이름까지 표기하도록 하겠다.
행 하나는 노드의 이름, 그리고 행 하나는 무한으로 (혹은 매우 큰 값으로) 각 항목들이 초기화된 표에서 시작하게 된다. 가령 a~e의 노드로 이루어진 그래프에서는 a에서 다른 노드로 가는 최소 비용 경로를 구한다고 할때 아래와 같은 표로 시작한다.
| a | b | c | d | e |
| 0 | Infinity | Infinity | Infinity | Infinity |
이러한 표는 출발점으로 삼고자하는 노드에서부터 탐색하지 않은 node를 선택하여 대상 node와 출발점 node를 비교하여 표와 대상 노드로 가는 최소값을 비교하여 표를 최신화 해나가면 된다.
위의 그래프 T를 대상으로 설명해보겠다.
| a | b | c | d | e |
| 0 | Min(4,Infinity) | Min(1,Infinity) | Infinity | Infinity |
- a를 시작점으로 선택하고 a에 연결된 edge의 가중치를 찾아서 표에 적힌 값과 비교하여 더 작은 것을 기재한다. 위 그림의 경우 b와 c의 경로 값이 Infinity에서 4와 1로 변경 된 것을 볼 수 있다.
| a | b | c | d | e |
| 0 | 4 | Min(1,4+6) | Min(4+2,Infinity) | Min(4+11,Infinity) |
- a 다음에 b 노드를 선택하여 연결된 edge의 가중치를 체크한다. a,c,d와 연결되어있는데 a는 이전 노드에서 체크했으니 그대로 두고 c,d,e에 대해서만 표와 비교하여 최소값을 취한다.
| a | b | c | d | e |
| 0 | 4 | 1 | Min(1+3,6) | Min(1+8,15) |
- 다음으로는 c와 연결된 노드를 체크하는데 a,b는 이전에 체크했으니 두고 d와 e노드에 대해서 최소값을 취해 표에 최신화 한다.
| a | b | c | d | e |
| 0 | 4 | 1 | 4 | Min(4+7,9) |
- 다음으로 d를 체크하는데 a,b,c는 했으니 e에 대해서만 최소 값을 취해 표를 최신화한다.
| a | b | c | d | e |
| 0 | 4 | 1 | 4 | 9 |
- 마지막 노드는 이미 이전 노드에서 연결된 부분을 다 확인했으니 처리할 것이 없다.
이 알고리즘은 간선의 가중치가 음수일때는 사용할 수 없다. 이는 항상 최소 가중치를 선택하는 알고리즘의 특성상 그러하다.
이러한 다익스트라 알고리즘은 어떻게 구현하느냐에 따라 시간 복잡도가 달라지는데 이전에 방문하지 않았던 edge중 가장 작은 것을 찾는데 선형 탐색으로 찾을 경우 최악의 경우 전체를 search 해야하므로 O(V^2)이다. 하지만 이러한 edge를 우선 순위 큐로 구현하여 찾을 경우 우선 순위 큐 자체가 log 탐색 시간을 보장하므로 시간 복잡도는 O(E log V)가 된다.
밸만 포드 알고리즘(Bellman-Ford algorithm)
다익스트라의 경우 선택하지 않았던 노드의 최소 값을 선택하기 때문에 음수 가중치가 되면 사용할 수 없었던 반면 벨만 포드 알고리즘의 경우 매번 전체를 다시 확인하기 때문에 음수 가중치에도 사용할 수 있는 알고리즘이다.
시작은 다익스트라와 비슷하다. 행 하나는 노드의 이름, 그리고 행 하나는 무한으로 (혹은 매우 큰 값으로) 각 항목들이 초기화된 표에서 시작하게 된다.
아무래도 음수에 대한 체크를 지원하는 알고리즘이고 음수를 추가 하지 않는다면 사실 다익스트라와 동일하게 나올 것이기 때문에 이번에는 음수 가중치를 포함한 위의 그래프로 예시를 들어보겠다.
이렇게 총 노드 개수 v에 대해 V-1번 순회 했을때 데이터가 나오는데 최소 V번 순회하게 되었을 때 가중치 배열의 값이 줄어든다면 음수 가중치가 있는 것이므로 벨만 포드 알고리즘에서는 결과를 구할 수 없다고 반환 가능하다.
노드 마다 전체 edge를 체크하므로 시간 복잡도는 O(VE)이다.
플루이드 워샬 알고리즘(Floyd-Warshall algorithm)
다익스트라와 벨만 포드 알고리즘이 한 개의 노드에 대해서 다른 노드까지의 최단 거리를 알 수 있는 알고리즘이었다면 플루이드 워샬 알고리즘의 경우 한번 시행으로 모든 노드간의 최단 거리를 알 수 있을 뿐더러 벨만 포드와 같이 음의 가중치를 가진 경우에도 사용 가능하다.
이번에는 다익스트라에서 사용하던 그래프를 사용하여 설명을 해보도록 하겠다.
기본적으로 플루이드 워샬 알고리즘의 경우 모든 노드가 중간 경유지로 설정될때를 가정해서 돌아간다. 그렇기 때문에 노드 개수가 N이라면 총 N번의 라운드가 돌아간다. 위의 그래프도 노드가 5개이니 총 5번의 라운드가 돌아가면 각 노드에서 노드간의 최단 거리는 2차원 배열로 나타난다.
초기에 N x N 크기만큼의 2차원 배열을 초기화한다. 이 초기화된 배열에는 인접한 노드의 경우 간선의 가중치가 나타나 있고 인접하지 않은 노드의 경우 Infinity로 나타나있다.
| a | b | c | d | e | |
| a | 0 | 4 | 1 | Infinity | 5 |
| b | 4 | 0 | 6 | 2 | 11 |
| c | 1 | 6 | 0 | 3 | 8 |
| d | Infinity | 2 | 3 | 0 | 7 |
| e | 5 | 11 | 8 | 7 | 0 |
- 첫번째 라운드에서 노드 a를 중간점으로 하여 최소 거리를 환산하면 아래와 같이 나온다. 변경된건 괄호 처리 해두었다.
| a | b | c | d | e | |
| a | 0 | 4 | 1 | Infinity | 5 |
| b | 4 | 0 | (5) | 2 | (9) |
| c | 1 | (5) | 0 | 3 | (6) |
| d | Infinity | 2 | 3 | 0 | 7 |
| e | 5 | (9) | (6) | 7 | 0 |
- 두번째 라운드에서는 노드 b를 중간점으로 하여 최소 거리를 환산하면 아래와 같이 나온다.
| a | b | c | d | e | |
| a | 0 | 4 | 1 | (6) | 5 |
| b | 4 | 0 | 5 | 2 | 9 |
| c | 1 | 5 | 0 | 3 | 6 |
| d | (6) | 2 | 3 | 0 | 7 |
| e | 5 | 9 | 6 | 7 | 0 |
이런식으로 5번의 라운드를 돌아가면 모든 노드가 각 노드에 대해서 도달하기 위한 최소 가중치가 산출된다. 노드의 개수가 N일때, N 단계를 수행하고 단계마다 O(N^2)의 연산을 통해 결과가 산출된다. 따라서 시간 복잡도는 O(N^3)이다.