[알고리즘] 최단경로(Shortest Path Problem) - 2

최단경로(Shortest Path Problem) - 2

위의 그림은 Bellman-ford 알고리즘의 예이다.

첫번째 라운드에서 모든 엣지들에 대해서 relax 한다.

relax연산이 끝나면 초기 시작점과 인접한 엣지들의 ∂값이 세팅된다.

이렇게 순차작으로 relax 연산을 실행한다.

위 그림은 한가지 실행 가능한 예이며, 어떠한 엣지를 선택하느냐에 따라서 다른 순서를 가진다.

이 Bellman-ford는 시간 복잡도에서 그리 좋은 알고리즘은 아니다.

위의 그림은 왜 Bellman-ford의 시간 복잡도가 비효율적인지 알려준다.

Bellman-ford 의 최악의 상황이 표현되었고, d[v]가 한번 갱신될때 마다 우측의 노드들의 값이 바뀐다.

이는 불필요한 계산이 증가한다는 것이고, 그에따른 오버 헤드도 증가한다.

다음은 좀 더 효율적인 다익스트라 알고리즘에 대해 알아보자

우선 초기화는 Bellman-ford 알고리즘과 동일하며, 엣지들에 대해 relax를 하는것도 같다.

그러나 모든 엣지들에대해 relax를 하는 것이 아니라 distance값이 최소인 값을 찾는다.

그 후, distance 값이 최소인 노드로 부터 나가는 엣지들만 relax를 실행한다.

이것이 다익스트라의 한라운드이다.

그리고 relax된 노드를 두번 선택할 필요는 없다.

이유는 해당 노드가 가지고 있는 d값이 이미 최단 경로이기 때문에, 다시 갱신할 이유가 없기 때문이다.

결과적으로, 한번 relax를 한 엣지에 대해서는 relax연산을 하지 않는다.

다익스트라 알고리즘의 특징으로 첫번째, 음수 가중치가 없다.

또한 S로 부터 최단 경로의 길이를 이미 알아낸 노드들의 집합 S를 유지한다.

따라서 맨처음에는 출발점만 있기 때문에 S={s}가 된다.

그러므로 모든 노드들의 최단경로의 집합이 S가 된다.

집합 S에 속해있지 않는 노드 u에 대한 d(u)는 

집합 S에 속해있는 노드들을 통해 u까지 갈수 있는 최단경로의 길이다.

위의 그림은 다익스트라 알고리즘의 실행도이다.

앞서 말했던것 처럼 자신과 인접하고 노드에서 나가는 엣지에 relax연산을 실행한다.

이렇게 f까지 연산을 완료하면 모든 노드에 대한 최단 경로가 찾아진다.

위의 슈도 코드는 다익스트라 알고리즘이다. 그 중 6번 라인까지가 초기화를 실행하는 코드이다.

반복문을 n-1번 수행하며 relax 연산으로 모든 노드까지의 최단 경로를 찾는다.

좀 더 자세하게 말하자면 방금 선택한 노드가 u라면 u에서 나가는 엣지에 relax연산을 해준다.

그리고 최단경로를 다시 탐색하여 해당 노드까지의 최단 경로에 넣어준다.

2개의 반복문으로 인해 시간복잡도는 O(n^2)가 된다.

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘