09. shortest path dijkstra algorithm [4 1주차]

9. Shortest Path - Dijkstra Algorithm [4-1주차]

2024년 1월 9일 화요일

오후 11:16

<Shortest Path 문제>

S에서 A, S 에서 B, …, S에서 D까지의 최단 거리를 모두 구하는 것이 목표.

 

여기서 그리디 작전을 사용하여, 매번 거리가 가장 작은 길을 선택한다면 어떻게 될까?

C로 갈 때는 거리가 5인 길을 선택하여 최단 거리를 찾을 수 있다. 10이나 6을 선택하면 이미 5보다 더 커지므로, 5를 선택하는 게 최단 거리가 맞다.

그러나 D로 가기 위해 매번 짧은 길을 선택하면 5+2의 거리가 되어, 6으로 갈 때보다 거리가 길어진다.

따라서 이 문제는 직관적인 Greedy 작전으로는 풀 수 없다.

 

Shortest Path를 푸는 알고리즘으로 Dijkstra Algorithm이 가장 유명함.

 

사용되는 원리 :

• 만약 S에서 T까지의 shortest path를 찾았다면, 경로 내의 A에서 B까지의 shortest path도 찾은 것. 만약 A에서 B까지의 더 빠른 경로가 있다면, S에서 T까지의 경로가 최소가 아니게 되므로 모순.

 

 

<Dijkstra Algorithm 의 종류>

1.     최단 경로의 가중치 합만 찾음

2.     실제 경로를 찾음.

3.     중복 정답이 있는 경우, 최단 경로들을 모두 찾음

 

 

<Dijkstra algorithm의 아이디어>

Prim알고리즘과 비슷함.

S에서 S로의 답은 0. 나머지는 아직 답을 모른다.

그러나 S에서 바로 갈 수 있는 노드로의 잠정적인 답을 구해 볼 수 있다.

(진짜 답은 아님. 나중에 답을 고쳐 나가는 방식으로 진행)

이 잠정적인 답 중 가장 작은 값을 가지는 것은 무조건 정답. 다른 정답이 있다면 S에서 나가는 다른 간선을 통해야 하는데, 이미 값이 더 커짐.

 

 

<Dijksetra 알고리즘 동작방식>

최단 거리가 구해진 노드를 빨간색으로 칠하고, 최단 거리의 추정값만이 구해진 노드를 파란색으로 칠하자.

 

알고리즘은 다음과 같이 동작한다.

1.   시작 노드 v₀ 로의 거리를 0라 하고, v₀를 빨간색으로 칠한다

2.     v₀에 인접한 노드마다 최단 거리 추정값을 구한다. 추정값은 v₀와 인접 노드를 연결하는 간선의 가중치와 같다.

3.     최단 거리 추정값 중 가장 작은 값은 무조건 정답이다. 해당 추정값을 가진 노드가 u라면, u를 빨간색으로 칠한다.

4.     u에 인접한 노드들에 대해 최단 경로 추정값을 갱신한다. 이때, u의 인접 노드 x의추정값은 (v₀~>u의 경로 길이) + w(u, x) 이다. 단, x가 원래 가지고 있던 추정값이 더 작다면, 갱신하지 않는다.

5.     3과 4를 모든 노드가 빨간색이 될 때까지 반복한다.

 

(노드 u, v를 연결하는 간선이 여러 개라면, 가장 가중치가 작은 것만을 고려)

 

v.d : 노드 v가 파란색이면 최단 거리 추정값. 빨간색이면 최단 거리 정답이 됨.

R : 노드를 빨간색으로 칠하는 것을 아래 코드에서는 집합 R에 노드를 넣는 것으로 표현한다.

 

Algorithm Dijkstra(그래프 G, 노드개수 n, 시작 노드 v₀, 답 d_min)

v₀.d = 0

R = {v₀}

for v₀에 인접한 노드 u에 대하여

u.d = w(v₀, u)

while |R| < n

u = R에 있지 않은 노드 중 d 값이 가장 작은 것

R = R U {u}

for u에 인접하고 R에 없는 노드 x에 대하여

x.d = min[x.d, u.d + w(u, x)]

 

 

<다익스트라 증명 (귀류법)>

노드 u가 R에 더해질 때, u는 d값이 최단거리가 아닌 최초의 노드라고 가정한다. v₀에서 u로의 최단 경로를 p라 하자. u를 R에 넣기 전, p에는 빨간색이 아닌 노드가 포함되게 된다. 알고리즘에서 빨간 노드의 인접 노드 중 빨갛지 않은 노드는 모두 파랗게 칠했으므로, p에는 파란 노드가 포함된다. p에서 최초의 파란 노드를 y라 하고, 그 직전원소를 x라 하자. p는 다음과 같이 표현된다.

p : v₀~>x->y~>u

(v₀=x, y=u일 수 있다. w(p)는 u까지의 최단거리)

노드 u는 d값이 최단거리가 아닌 '최초의' 노드이므로 x.d는 x로의 최단거리다.

또한 y로의 최단 경로는 p의 부분 경로 p' : v₀~>x->y 이다. 왜냐하면, p'보다 더 짧은 경로가 있다면, p가 최단 경로가 아니게 되기 때문이다. 따라서 w(p') = x.d + w(x, y) 은 y로의 최단 길이이며, 이 값은 x가 R에 추가된 이후 y.d에 저장된다. 즉, y.d에는 y로의 최단 길이가 저장되어 있다.

y.d = w(p') <= w(p) <= u.d

(w(p) <= u.d인 이유는 d값은 최소 길이보다 작아지지 않기 때문)

그런데 알고리즘에서는 d값이 가장 작은 파란 노드를 선택하므로, u.d<=y.d 여야 한다. 따라서 y.d = u.d, w(p)=u.d 가 된다. 이는 u.d가 최단거리가 아니라는 가정에 모순이다.

 

 

<실제 '경로'를 찾는 법>

위 코드는 경로의 길이는 구하지만 경로 자체는 구하지 못한다. 경로 자체를 구하려면, 노드의 숫자가 업데이트될때마다, 그 노드를 업데이트시킨 직전 노드를 저장하면 된다.

• shortest path tree : 하나의 정답 경로만 저장
• shortest path DAG : 답이 여러 개라면, 특정 노드로의 최단 경로를 모두 저장.

x.d > u.d + w(u, x) 인 경우 저장된 값을 업데이트 하고,

x.d = u.d + w(u, x) 인 경우 직전원소를 추가로 저장

 

 

<dijkestra 시간복잡도>

Algorithm Dijkstra(그래프 G, 노드개수 n, 시작 노드 v₀, 답 d_min)

v₀.d = 0

R = {v₀} ->O(1)

for v₀에 인접한 노드 u에 대하여 ->O(n)

u.d = w(v₀, u)

while |R| < n  -> n번 반복됨

u = R에 있지 않은 노드 중 d 값이 가장 작은 것

-> O(logn). priority queue 사용

R = R U {u} ->O(1)

for u에 인접하고 R에 없는 노드 x에 대하여

-> while문까지 고려, 간선 개수 m * 2 번 실행됨

x.d = min[x.d, u.d + w(u, x)]

-> priority queue 를 수정해야 함. O(logn)

-> 따라서 총 O(mlogn)

 

전체 시간 O(mlogn)

 

 

<BFS 를 이용한 증명>

너비 우선 탐색을 이용한 다익스트라 알고리즘 증명도 있다.

가중치가 5인 간선에 노드 4개를 끼워넣는 식으로 간선의 가중치를 모두 1로 만든다.

 

 

 

 

이 상태에서 너비 우선 탐색을 하면 shortest path가 구해진다.

 

 

<다익스트라 알고리즘의 특징>

시작 노드s, 직전에 R에 들어간 노드u, 지금 R에 추가하려는 노드 v가 있다. 이때, u.d<=v.d이다. 만약 u.d>v.d라면, u가 R에 v보다 먼저 추가될 수 없기 때문이다. u가 추가되면서 v.d값이 더 작아진다고 하더라도, v.d = u.d + w(u, v) 이기 때문에 u.d<v.d 이다.

따라서 다익스트라 알고리즘은 가까운 노드를 먼 노드보다 먼저 R에 추가한다는 것을 알 수 있다.

 

 

<Dijkestra와 Prim의 비교>

Prim 알고리즘은 가장 작은 간선을 추가하지만, Dijkestra 알고리즘은 가장 경로가 작은 노드를 추가한다.