최단경로 알고리즘

[hokeunoh]

방향 그래프 G=(V,E)에서 n개의 정점이 존재하고 연결선에 가중치(weight)가 주어졌을 때 시작 정점 Vi에서 종착 정점 Vj에 도달하는 여러 경로 중에서 가장 짧은 경로 즉, 가중치의 합이 최소인 경로를 최단 경로(shortest path)라고 한다. (최소 비용 스패닝 트리와는 달리 시작이 있고 끝이 있음에 주의하라)

이 문제를 이야기할 때 나오는 단골손님이 바로 외판원 문제이다. 외판원이 주변의 모든 집을 돌면서 영업을 해야 하는 상황이다. 외판원은 일하는데만도 피곤한 상황이다. 외판원이 어떻게 하면 가능한 한 적은 걸음으로 모든 집을 돌 수 있을까? 이것이 바로 최단경로의 문제이다.

이러한 최단경로를 구하기 위한 알고리즘에는 Floyd 알고리즘과 Dijkstra 알고리즘이 있다.

최소 비용 스패닝 트리를 구할 때 쓰인 알고리즘들(Kruskal, Prim, Sollin)은 무방향 그래프(Undirected Graph)에만 적용되는 것이나, 본 Floyd알고리즘과 Dijkstra알고리즘은 화살표가 있는 방향 그래프(Directed Graph)에 적용되어 최단 경로를 찾아낸다. 그러나 이 알고리즘들이 방향 그래프에만 적용되는 것은 아니다. 무방향 그래프에도 쓰이기는 한다. 그러나 시작점이 있고 끝이 있으며 최단경로로 이동하려 할 때 방향이 없다고 해서 역방향으로 이동하는 일은 없을 것이다. 그러므로 사실상 시작점에서 끝점을 향하여 방향이 있는 것으로 봐야 할 것이다.


최단 경로를 구하는 대표적인 알고리즘을 나열하였다. 하나씩 살펴보자.

다익스트라 알고리즘 (Dijkstra Algorithm)
플로이드 알고리즘 (Floyd Algorithm)


Dijkstra의 알고리즘은 V에서부터 다른 모든 정점들까지 증가하는 거리의 순으로 최단 경로를 찾을 수 있다. 이 알고리즘은 팡의 최소 스패닝 트리 알고리즘에서처럼 정점 V에서 시작하여 새로운 정점들로 도달하는 특정한 에지들을 선택하면서 분기해 나간다. 또한 항상 가장 가까운 거리를 갖는 정점으로의 에지를 선택한다. 그리고, 각 인접 정점에 대해 오직 하나의 후보 에지만을 추적한다.
예를 들어, 어떤 회사에서 1000만원짜리 기계와 100만원짜리 기계중에 하나를 꼭 구입해야 하는 상황에 빠져 있을 때, Greedy는 말그대로 가장 싼것을 택하는 것이다. 1000만원짜리 기계를 써서 1억원이 넘게 벌수 있고, 100만원짜리를 써서, 10만원도 벌지 못한다 하더라도, 우선 뒤를 생각하지 않고 무조건 지금 상황에서의 최적만을 찾는 것이다. 그런 의미에서 Greedy라는 알고리즘은 항상 최적해를 뽑아내지 못하는 경우가 많다. 따라서, Greedy방법으로 최적해를 해결하고자 할 때 사용되는 선택규칙이 궁극적으로 최적해를 구해낸다는 것에 대한 증명이 반드시 뒷받침 되어야 한다.

Dynamic이라는 것은 Divide and Conquer의 반대말이다. Divide and Conquer는 큰 문제를 먼저 작은 문제들로 분할하고 각각 해결해나가는 것인데 반해, Dynamic은 작은 문제를 먼저 해결하고, 그 결과를 저장한 다음, 후에 똑같은 계산을 반복하는 대신, 그 저장한 결과를 이용하는 방식이다. 따라서 메모리가 많이 필요하다는 것이 Dynamic의 단점이다.




<그래프>
위와 같은 그래프에서 1에서 시작해서 8로 가는 최단거리를 Dijkstra알고리즘을 이용해서 구해보자. 먼저 위의 그래프를 인접행렬로 바꾼다.

∞ 값은 연결되지 않은 부분을 나타낸 것으로 실제로는 충분히 큰 값을 넣으면 된다.

동작방법은 다음과 같다.

1. 처음에 출발마디를 선택하여 각 마디까지의 임시최단거리를 표시하되, 직접 연결되는 가지가 없으면 ∞로 표시한다.
2. 선택되지 않은 마디에 대하여, 가장 작은 임시최단거리를 갖는 마디를 선택하고 연결하여 영구최단거리로 삼는다. 도착마디가 선택되면 끝내고, 아니면 3단계로 간다.
3. 선택되지 않은 마디에 대해, 직전에 선택된 마디와 연결될 때의 거리가 기존의 임시최단거리보다 작으면 임시최단거리를 수정하여 2단계로 간다.



1 단계 - 경로 1에서 시작한다. 경로 2나 경로 6으로 갈 수 있는데 가장 가까운 경로인 2로 간다. 가중치는 2이다. 경로 2로 갔으므로 다음에 경로 3이나 경로 4로 갈 수 있다. 따라서 무한대였던 경로 3과 경로 4의 임시최단거리를 수정해야 한다.
경로 3의 임시최단거리는 무한대에서 2 + 4 = 6 으로 수정되었다.
경로 4의 임시최단거리는 무한대에서 2 + 1 = 3 으로 수정되었다.



2 단계 - 경로 4와 경로 6의 가중치값은 3으로, 가장 작다. 먼저 경로 4로 가게 되면 경로 5와 7의 임시최단거리가 수정된다.
경로 5의 임시최단거리는 무한대에서 3 + 3 = 6 으로 수정되었다.
경로 7의 임시최단거리는 무한대에서 3 + 2 = 5 로 수정되었다.


3 단계 - 경로 6으로 간다. 경로 6에서도 경로 7로 갈 수 있지만 임시최단거리는 수정하지 않는다. 왜냐하면 현재 경로 7의 가중치값은 5인데 반해, 경로 1에서 경로 6을 거쳐 경로 7로 가게되면 그 거리는 3 + 6 = 9 가 되기 때문이다. 값이 더 크므로 경로 7의 임시최단거리에는 아무런 영향을 미치지 못한다.


4단계 - 경로 7의 임시최단거리가 5 이므로 경로 7로 간다. 이제 최종 목표인 경로 8에 접근할 수 있게 되었다. 경로 8의 임시최단거리를 5 + 4 = 9로 수정한다.


5단계 - 임시최단거리가 가장 짧은 곳은 경로 3과 경로 5로써 그 값은 6이다. 먼저 경로 3으로 간다. 이때 경로 3에서도 경로 5로 갈 수 있는 길이 생겼지만 가중치값이 더 크므로 임시최단거리는 수정되지 않는다.


6단계 - 경로 5로 간다. 이제 경로 5에서도 경로 8로 갈 수 있는 길이 생겼지만 가중치값이 더 크므로 임시최단거리는 수정되지 않는다.


7단계 - 드디어 최단경로를 다 찾았다. 경로 1 - 2 - 4 - 7 - 8 로 갈 때 가중치가 9로 최소가 된다.

본 애플릿은 Dijkstra 알고리즘을 구현한 것이다. 동작 방법을 설명한다.

New Problem 버튼 : 이 버튼을 누르면 랜덤하게 그래프가 생성된다. 기존의 자바 애플릿은 한 가지 경우의 그래프만을 가지고 실습을 해야 했기에 설명을 듣고 난 후 다른 Case에서 실습해 보기가 힘들었다. 그러나 이 애플릿을 통해 이용자는 알고리즘이 확실히 이해될 때 까지 다양한 그래프에서 동작을 시험해 볼 수 있다.
Step Solve 버튼 : 말 그대로 한 노드씩 탐색을 하는 것이다.
Solve All 버튼 : 이 버튼을 누르면 한번에 최소비용 스패닝 트리를 찾아낸다.

이밖에 상태를 나타내는 바에서 동작상황을 알 수 있으며 화면 왼쪽 위의 회색 화살표를 보면 어느 노드에서 어느 노드로 탐색이 이루어졌는지 표시된다. 또한 탐색한 총 비용이 Sum of Cost에 합산되어 출력된다. 그리고 노드와 노드사이가 1줄로 연결된 것이 아니라 2줄로 연결된 곳이 있다. 이는 한 노드에서 다른 노드로 갈 때와 올 때의 비용이 서로 다름을 의미한다. 예를들어 1번 노드에서 2번 노드로 갈 때는 1의 비용이 드는데, 2번 노드에서 1번 노드로 갈 때는 8의 비용이 들 수 있다. 오르막길을 생각하면 되겠다. 하늘색의 작은 상자는 1번 노드에서부터의 최단 경로 비용을 나타낸다.

본 애플릿은 많은 수의 클래스파일과 그림을 로딩하기 때문에 로딩시에 20초에서 1분정도의 시간이 걸릴 수 있다. 다운된 것이 아니므로 기다리면 애플릿을 볼 수 있다.



Dijkstra 알고리즘이 Greedy한 방법이었다면 Floyd 알고리즘은 동적계획법이 들어간 보다 고차원적인 알고리즘이라 할 수 있다. 혹자는 Dijkstra 알고리즘이 나중을 고려치 않음을 보며 단순무식하다(?)고 평하기도 한다.

최적해를 구하는 문제를 푸는 방법들은 의례적으로 여러 단계를 거치게 되고, 각 단계에서는 일반적으로 선택을 하게된다. 이러한 최적해를 구하는 문제들은 동적 계획법을 적용하면 모든 경우에 최적해를 구할 수 있지만, 더욱 간단하고 효과적인 Greedy 방법에 의해 해결되는 문제들도 많이 있다. Greedy 방법은 최적해를 구하는 문제를 풀기위해서 행하는 각 단계에서의 선택시, 그 단계에서의 상황만 고려해서 최선의 선택을 한다. 즉, 최적해를 구하기위해서 각 단계에서 최선의 선택만 하면 궁극적으로 최적해를 구할 수 있기를 바라는 것이다. 물론, 구할 수 없는 경우도 많이 있겠지만, 실제, 이런 방법으로 해결될 수 있는 최적화 문제들이 상당히 존재한다.

이런 문제들에 대해서 동적 계획법을 적용하여 문제를 해결하려 하는 것은 시간과 노력의 낭비가 아닌가 하는 입장도 있지만 실제 프로그래머의 입장에서 보면 Dijkstra알고리즘보다 본 Floyd알고리즘이 코딩면에서 훨씬 간단하다. 어차피 계산은 컴퓨터가 하는 것이므로 간단한 코딩이 더 선호될 수도 있다.

그런데 더욱 재미있는 것은 실제 성능에서도 Floyd 알고리즘이 앞선다는 것이다. Dijkstra 알고리즘의 시간복잡도가 O(n^2) 인데 반해 플로이드 알고리즘은 O(n^3)이다. 이것만 봐서는 Floyd 알고리즘이 더 느릴 것이라고 생각하기 쉽다. 하지만 Dijkstra 알고리즘이 한번의 루프를 돌 때마다 하는 일이 많다보니(복잡하다보니) 실제로는 Floyd가 빠른 경우가 상당히 많다.


동작원리 자체는 매우 간단하다. A에서 B로 갈 수 있는 경로가 있고, 또한 B에서 C로 갈 수 있는 경로가 있다고 한다면 결국 A에서 C로 갈 수 있는 경로가 있다고 할 수 있다. 만약 A에서 C로 '직접' 갈 수 있는 경로가 원래 존재했는데 직접 갈 때의 비용이 B를 거쳐 C로 가는 것보다 많이 든다고 하자. 그러면 플로이드 알고리즘에서는 A에서 C로 가는 것을 폐기하고 A에서 B를 거쳐 C로 가는 '최단거리' 로 업데이트를 하게 된다.

<위의 그래프에 대해서 플로이드 알고리즘을 적용해보자>

본 애플릿은 Floyd 알고리즘을 구현한 것이다. 동작 방법을 설명한다.

New Problem 버튼 : 이 버튼을 누르면 랜덤하게 그래프가 생성된다. 기존의 자바 애플릿은 한 가지 경우의 그래프만을 가지고 실습을 해야 했기에 설명을 듣고 난 후 다른 Case에서 실습해 보기가 힘들었다. 그러나 이 애플릿을 통해 이용자는 알고리즘이 확실히 이해될 때 까지 다양한 그래프에서 동작을 시험해 볼 수 있다.
Step Solve 버튼 : 말 그대로 한 노드씩 탐색을 하는 것이다.
Solve All 버튼 : 이 버튼을 누르면 한번에 최소비용 스패닝 트리를 찾아낸다.

이밖에 상태를 나타내는 바에서 동작상황을 알 수 있으며 화면 왼쪽 위의 회색 화살표를 보면 어느 노드에서 어느 노드로 탐색이 이루어졌는지 표시된다. 또한 탐색한 총 비용이 Sum of Cost에 합산되어 출력된다. 그리고 노드와 노드사이가 1줄로 연결된 것이 아니라 2줄로 연결된 곳이 있다. 이는 한 노드에서 다른 노드로 갈 때와 올 때의 비용이 서로 다름을 의미한다. 예를들어 1번 노드에서 2번 노드로 갈 때는 1의 비용이 드는데, 2번 노드에서 1번 노드로 갈 때는 8의 비용이 들 수 있다. 오르막길을 생각하면 되겠다. 하늘색의 작은 상자는 1번 노드에서부터의 최단 경로 비용을 나타낸다.

본 애플릿은 많은 수의 클래스파일과 그림을 로딩하기 때문에 로딩시에 20초에서 1분정도의 시간이 걸릴 수 있다. 다운된 것이 아니므로 기다리면 애플릿을 볼 수 있다.

[출처] 그래프 알고리즘 정리|작성자 짱보이