[알고리즘] ep7) 최단경로

ㅁ최단경로 문제(shortest path problem): 가중그래프 두 개의 정점 u와 v가 주어졌을 때, u와 v 사이의 무게의 합이 최소인 경로를 구하는 문제

최단경로길이: 간선들의 무게 합

예시: 동경과 로마 사이의 최단경로

 

응용: 인터넷 패킷 라우팅, 항공편 예약, 자동차 네비게이션

 

[최단경로 속성 2가지]

속성1)

최단경로의 부분경로(subpath) 역시 최단경로이다

 

속성2)

출발정점으로부터 다른 모든 정점에 이르는 최단경로들의 트리가 존재한다 - 단일점 최단경로(single-source shortest path)

예시: 동경으로부터의 최단경로

 

 

<MST와의 비교>

- 최단경로는 무방향뿐만 아니라 방향그래프에서도 정의가 가능하다

- 그래프에 음의 무게를 가진 싸이클이 있거나, 무방향그래프에 음의 무게를 가진 간선이 있으면 부정한다

- 최단경로트리(shortest path tree)는 루트트리이다

MST의 예

 

 

(주의)

가중 방향그래프에 음의 무게를 가진 싸이클이 존재한다면, 최단경로는 존재하지 않는다

 

 

 

[최단경로 알고리즘 정리]

 

 

 

ㅇ다익스트라(Dijkstra) 알고리즘: 둘러보면서 작은 값으로 바꾸는 알고리즘 (그리디 알고리즘 / DP 일부)

우선순위 큐 사용 - 힙: O(m log n) / 무순리스트: O(n^2)

 

전제: 무방향 간선 + 간선의 무게 음수 X

s로부터 시작하여 정점들을 차례로 배낭에 넣다가 결국엔 모든 정점을 배낭에 넣는다

각 정점 v에 라벨 d(v)를 저장하여 배낭과 인접 정점들을 구성하는 부그래프에서 s로부터 v까지의 거리를 표현

반복의 각 회전에서 배낭 밖의 정점 가운데 거리 라벨 d가 최소인 정점 u를 배낭에 넣는다, 그리고 u에 인접한 정점들의 라벨을 갱신한다

 

배낭: 가상이므로 구현하지 않는다

우선순위 큐가 배낭 밖의 정점들을 보관한다 (key: 거리, element: 정점)

각 정점 v에 두 개의 라벨을 저장한다

- 거리(distance): d(v)

- 위치자(locator): 우선순위 큐에서 v의 위치

 

간선 완화(edge relaxation): 특정 경로를 따라 이동할 때 더 짧은 경로를 발견하면 경로의 비용을 갱신하는 과정

• 현재 정점(u)에서 인접 정점(v)으로 가는 간선(u, v)을 선택
• 간선(u, v)을 통해 인접 정점(v)으로 가는 새로운 경로의 거리를 계산
• 새로운 경로의 거리가 기존에 알려진 거리보다 짧다면, 정점(v)의 거리를 갱신

예시)

간선 e = (u, z)

 

 

 

u는 가장 최근에 배낭에 들어간 정점이고 z는 배낭 밖에 존재

간선 e의 완화를 통해 거리 d(z)를 갱신한다

 

 

(다익스트라 알고리즘 과정)

과정1

과정2

 

 

다익스트라 알고리즘은 탐욕법에 기초한다 따라서 거리가 늘어나는 순서로 정점을 배낭에 삽입한다

 

[모순법 증명]- 다익스트라 알고리즘이 정확한 이유

알고리즘이 모든 정점에 대한 최단경로를 찾지는 못했다고 가정하고, F를 알고리즘이 잘못 처리한 첫 번째 정점이라고 하자

올바른 최단경로 상의 이전 노드 D가 고려될 때, D의 거리는 정확했으며 이 값에 기초하여 간선 (D, F)가 완화되었다

그러므로 d(F) >= d(D)가 성립하는 한 F의 거리는 틀릴 수가 없다 - 즉, 거리가 잘못 계산된 정점은 있을 수 없다!

 

음의 무게를 가진 간선에 대해서 정확하게 작동하지 않는 이유는 무엇일까?

음의 부착간선을 가진 노드를 배낭에 넣으면, 이미 배낭 속에 있는 정점들의 거리를 혼란케 한다

C의 올바른 거리는 1이지만, d(C) = 2를 가지고 이미 배낭속에 있다

 

그럴싸한 해법)

1. 모든 간선의 무게에 상수 k를 더하여 음의 무게를 없앤다

2. 생성된 새로운 그래프에 대한 최단경로를 구한다

3. 원래 그래프에 맞게 결과를 보정한다 (즉, 모든 정점의 거리 라벨값에서 해당 정점에 이르는 최단경로상의 간선 수만큼 k를 뺀다)

 

 

ㅇ벨만-포드(Bellman-Ford) 알고리즘: 범용성은 넓지만 시간이 더 오래 걸리는 알고리즘 (DP 알고리즘)

우선순위 큐 사용 x

 

전제: 방향 간선 + 간선의 무게 음수 O

총 n - 1회의 반복을 수행하며 반복 라운드마다 모든 간선을 완화시도

i번째 반복 라운드에서 i개의 간선을 사용하는 최단경로를 찾는다

인접정보를 사용하지 않으므로 간선리스트 구조 그래프에서 수행 가능하다 (간선을 중심으로 작동하기 때문)

 

또한 알고리즘을 확장하면, 음의 무게를 가지는 싸이클이 있는지에 대한 여부도 확인 가능

 

과정1

과정2

 

 

ㅇDAG에서의 최단경로 - 위상순서(topological ordering)

별다른 데이터구조 사용 X

 

전제: 방향 간선 + 간선의 무게 음수 O

다익스트라 알고리즘보다 훨씬 빠르다 O(n + m)

과정1

과정2

 

 

 

[모든 쌍 최단경로(all-pairs shortest paths) 문제]

가중 방향그래프 G의 모든 정점쌍 간의 거리를 찾는 문제

- 그래프에 음의 무게를 가진 간선이 없다면, 다익스트라 알고리즘을 n번 호출할 수도 있다 - O(nm log n)

- 그래프에 음의 무게를 가진 간선이 있다면, 벨만-포드 알고리즘을 n번 호출할 수도 있다 - O(n^2m)

 

대안: DP를 사용하면 O(n^3) 시간에 수행 가능 (플로이드-와샬 알고리즘과 유사한 방식으로 수행)

 

 

정점들을 1, 2, ..., n으로 번호를 매기고 1, 2, ..., k로 매겨진 정점들만 경유 정점으로 사용하는 경로들을 고려한다

시간복잡도: O(n^3) - 여기서 n은 정점의 수

 

 

과정1

과정2

과정3

과정4

 

 

 

 

 

 

 

 

출처 및 참고: 알고리즘-원리와 응용(국형준교수님), Algorithm Design(Jon Kleinberg, Eva Tardos), Foundations of Algorithms using C++(Richard Neapolitan)