알고리즘 공부 <12> - 최단경로 (Bellman-Ford,Dijkstra)

지난번 공부했던 Minimum Spanning Tree는  최소비용에 초점을 맞춰 트리를 구성하는 것이었다.

이번에는 최단경로를 구한후 이에 대한 가중치를 구하는 최단경로 알고리즘을 공부해보자

1. Single-Source Shortest Path

가중치가 있는 방향 그래프가 있다. 여기서  시작점 S에서 다른 노드 V 까지의 최소가중치 경로 즉 최단경로를 찾아야 한다. 

이후 찾은 최단경로의 가중치는 간선들의 총합이 된다.

여기서  optimal substructure라는 중요 속성을 가지게 되는데 이는 최당경로 안에 있는 서브패스 역시 최단경로가 된다는 것이다. 잠깐 이를 증명해보이고 가겠다

명제 A : 최단경로(P)의 어떤(모든) 서브패스는 최단경로이다 

~A : 최단경로(P)의 몇몇 서브패스는 최단경로가 아니다.  

여기서 ~A는 True 라 가정하고 이후 ~A가 contradiction임을 증명해보이면 된다.

~A에 따라  P(a,b)는 최단 경로가 아니다.  즉 최단경로 P`(a,b)인 다른 최단경로가 존재한다

따라서 w(P(a,b)) > w(P`(a,b)) 가 되고 이를 단순하게 대체하면 최단경로P의 서브패스 P`(a,b)에 대해 w(P) > w(P`)가 있는 것을 의미하며 이는 최단경로가 존재함을 의미함으로 ~A는 false가 된다.  즉 ~A 명제는 contradiction이 되므로 따라서 명제 A는 true가 된다.

2. Bellman-Ford Algorithm

그럼 이번에는 최단경로를 구하는 알고리즘에 대해 공부해보자

먼저 이 알고리즘 역시 먼저 초기화 과정을 거친다. 모든 노드에 대하여 그 노드까지의 거리를 전부 무한대로 초기화 이후

시작점s에 대해서만 0으로 초기화한다.

이후 (노드-1) 즉 엣지의 개수 만큼 수행하게 되는데 이 때 가장먼저 소스와 인접노드에 가중치 값이 업데이트 되어진다.

이후 인접노드에 대해서 Relax( 시작점에서 현재 노드까지의 가중치 + 목표지점과의 간선에대한 가중치 와 현재 목표지점의 가중치를 비교하여 작은값을 목표지점의 가중치값에 대체하는것) 과정을 거치게 된다. 

모든 노드에 대한 가중치를 찾게 되면 끝이난다

이후 다시 처음부터 노드에 대한 가중치를 검사하는데 이때 노드간 사이클이 되어선 안된다. 사이클이 되는경우 no sulution을 리턴하게 된다.

빅오는 O(V*E)가 된다.

3. Dijkstra’s Algorithm

다익스트라 알고리즘 prim 알고리즘과 비슷하다 다만 prim과 다른점은 이전경로에 대한 누적된 가중치 값과 목표지점 노드의 가중치 값과 비교한다는 점이 다르다.

즉

빨갛게 칠한부분만 다르게 된다.

최단경로 역시 prim알고리즘과 동일하다 (http://history1994.tistory.com/48)