알고리즘 공부 - 최단경로

안녕하세요. yeTi입니다.
오늘은 알고리즘 공부 중 최단경로(Shortest Path)에 대해 학습한 내용을 공유하려고 합니다.
강의 : 권오흠 교수님의 2015 봄학기 알고리즘

개요

가중치 그래프에서 경로상의 모든 엣지의 가중치의 합이 가장 작은 경로 (u, v)를 찾는 방법입니다.

이전 그래프 탐색 - BFS에서 그래프에서 BFS를 활용하면 최단 경로의 길이를 구할 수 있다는 내용이 있습니다. 현재 다루는 최단경로(Shortest Path)와 차이점은 그래프에서 BFS 탐색시 찾을 수 있는 최단 경로의 길이는 엣지의 갯수이고 최단경로(Shortest Path)는 가중치의 합이라는 것입니다.

최단경로문제는 다음과 같은 유형이 있습니다.

• Single-source: 하나의 출발노드에서 다른 모든 노드까지의 최단 경로, Dijkstra's algorithm
• Single-destination: 모든 노드로부터 하나의 노드까지의 최단 경로, Single-source 문제와 동일
• Single-pair: 하나의 출발노드 및 하나의 목적지 노드까지 최단 경로, 최악의 경우 시간복잡도에서 Single-source 문제보다 나은 알고리즘이 없음
• All-pairs: 모든 노드 쌍에 대한 최단 경로, Floyd–Warshall algorithm

알고리즘에 따라 음수 가중치를 허용여부가 다르므로 문제 해석시 주의할 필요가 있고 음수 사이클(negative cycle)의 존재 여부에 따라 알고리즘의 동작 여부를 확인할 필요가 있습니다.

Single Source

Single Source Problem을 해결하는 기본적인 아이디어는 각 노드의 가중치를 무한대로 설정 후 전 노드의 가중치와 엣지의 가중치의 합이 현 엣지의 가중치보다 작으면 가중치를 조정해 나가는 것입니다. (relaxation)

알고리즘들 간의 차이는 어떤 엣지에 대해서, 어떤 순서로 relaxation을 하느냐의 차이입니다.

이를 표현하기 위한 기존 용어들은 다음과 같습니다.

• d[v] : 각 노드 v에 대한 가중치의 합
• π[v] : s에서 v까지의 최단경로상에서 v의 직전 노드(predecessor)
• δ(s, v) : s에서 v까지의가중치의 합

Generic Single Source 알고리즘

시작 엣지부터 연결된 모든 엣지에 대해 Relaxation을 수행하는데 모든 노드의 가중치에 변화가 없을때까지 수행하는 방식입니다.

한 예시로 Bellman–Ford algorithm이 있습니다.

Bellman–Ford algorithm은 엣지의 수만큼 반복하는데 매회 모든 엣지에 대해 relaxation을 수행하므로 시간복잡도는 O(nm)입니다.

Dijkstra's algorithm

Dijkstra's algorithm은 bellman–Ford algorithm을 개선한 방식입니다.

차이점은 가중치에 변화가 없을때까지 매 라운드마다 모든 노드에 대해 relaxation을 수행하던 방식을, 모든 노드에 대해 한번씩 relaxation을 수행하는데 매 라운드마다 선택한 노드의 인접 엣지에 대해서만 가중치 연산을 하는 것입니다.

이렇게 되면 기존 모든 노드에 대해 매번 엣지 연산을 하는 시간복잡도 O(nm)에서 모든 노드에 대해 연관 엣지만 연산하는 시간복잡도 O(mlogn)으로 개선할 수 있습니다. 해당 시간복잡도는 prim's algorithm 처럼 이진 힙 우선순위 큐를 사용할 경우이고, fibonacci heap을 사용하면 O(nlogn+m)의 시간복잡도를 가질 수 있습니다. 그렇지 않다면 기본적으로 O(n^2)의 시간복잡도를 가집니다.

다만 특이점은 음수 가중치가 없다고 가정한 알고리즘 입니다.

위 내용을 일반적인 식으로 나타내보면, 출발 노드 s로부터 최단경로의 길이를 알아낸 집합 S에 대해서 집합 V-S의 원소 중 최소 가중치를 가진 노드를 추가한 경로를 d(u)로 정의하고 그 밖의 노드를 추가한 가중치를 d(v)로 정의할 때, 노드 u에 대해서 d(u)는 노드 s에서 u까지가는 최단 경로입니다.

왜냐하면 집합 S에서 u까지가는 다른 최단 경로가 존재한다고 가정을 하면 중간에 추가적인 경로가 존재한다는 의미이고 이는 d(v)가 되는데 d(v)는 d(u)보다 큰 가중치를 가졌으므로 최소 가중치를 기질 수 없어 모순된 주장이 됩니다.

Floyd–Warshall algorithm

Floyd–Warshall algorithm은 동적 계획법(dynamic programming)에 기반한 알고리즘으로 순환식을 세우고 해당 순환식을 푸는 방식으로 문제를 해결하는 방법입니다.

앞서 언급했듯이 모든 노드 쌍에 대한 최단 경로를 구할 때 사용할 수 있고 시간복잡도는 O(n^3)을 가집니다.

다르게 생각해보면 Dijkstra's algorithm을 모든 노드를 대상으로 구현할 수도 있지만, 시간복잡도가 쉽게 구현했을 때 O(n^4)를 가지므로 비효율적입니다.

순환식의 아이디어는 간단합니다. 현재 노드를 포함한 경로와 포함하지 않은 경로 중 작은 가중치를 가진 경로를 선택하는 방식을 가집니다.

구현에 특이점은 2차원 배열을 활용하여 각 경로의 가중치를 저장할 수 있고 가중치뿐만 아니라 경로도 알고 싶다면 2차원배열을 하나 추가하여 경로의 순번을 저장하면 됩니다.

관련 강의

• [알고리즘] 제16-1강 최단경로(shortest path problem)
• [알고리즘] 제16-2강 최단경로(shortest path problem) (계속)
• [알고리즘] 제16-3강 최단경로(shortest path problem) (계속)

관련 글

• 알고리즘 공부 - 최소비용신장트리
• 알고리즘 공부 - 그래프
• 알고리즘 공부 - 해싱
• 알고리즘 공부의 필요성
• 알고리즘 공부 - 트리
• 알고리즘 공부 - sort
• 알고리즘 공부 - recursion
• 알고리즘을 공부해야하는 이유