[Greedy Algorithm] Shortest Path

Dijkstra Algorithm

Version of Dijkstra

• Only Shortest Path Length for each Node 경로를 구하는 것이 아니라 길이를 구하는 것
• Actual Path for each Node also 패스 노드까지 구함
• All possible Shortest Paths for each Node 모든 shortest path를 구함 - compact하게 표현하는 방법이 필요함

Alternate Explanations

• As a Variation of BFS
• Select from Nearest to Furthest

계속 짧은 길을 붙여나가는 방식은 shortest path를 찾을 것 같지만, 그렇지 않다. 

Shortest Path기 때문에 prim 처럼 풀 수 없다. 

 

Shortest Path

src에서 dst로 가는 가장 짧은 길을 찾는 것이 아니다. 

src에서 다른 모든 노드로 가는 가장 짧은 길을 찾는 것이다. 

그 이유는, dst까지 가는 shortest path를 찾으려면, 그 사이 과정도 모두 shortest path여야한다.

따라서 shortest path의 모든 일부분은 다 shortest path다

 

shortest path 증명하기 / 생각하기

 

당연히 우리는 1이 가장 최소 길이라고 생각할 수 있다. 

 

<귀류법>

만약, 저게 shortest path가 아니라면, 다른 곳을 통해서 가야한다. 

다른 곳으로 출발하게 되면, 시작부터 1보다 크기 때문에 더 짧은 길이 생길 수가 없다 

 

(일반화하는 것은 아니고 현재는 이렇게 증명 가능하다)

 

 

 

 

 

 

 

Dijkstra (Only Length)

Algorithm Dijkstra (G, n, \(v_0\), \(d_{min}\))

G = (V,E) 그래프

n = 노드 개수

\(v_0\) = source

\(d_{min}\) = 답, 출력, shortest path

따라서 모든 노드마다 \(d_{min}\)이 존재한다.

For u ∈ V do \(d_{min}(v)\) <- g(\(v_0\), u) 는 edge weight이다. no edge인 경우, 무한대∞라고 생각

g(\(v_0\), \(v_0\)) = 0 이다. 

 

Red : \(d_{min}(v)\)가 최종 정답

R <- {\(v_0\)}

while |R| < n do (red set에 있는 노드를 하나씩 늘려가서 모두 red가 되면 끝남)

• Among nodes not in R, find u with smallest \(d_{min}(u)\)
• R <- R \(\cup\) {u}
• For w not ∈ R do \(d_{min}(w)\) <- min [\(d_{min}(w)\), \(d_{min}(u) + g(u,w)]
• Blue : \(d_{min}(v)\)는 red set만 거치는 shortest path의 길이 (red set을 다 거치는 것이 아니라 blue를 거치지 못하는 것)

즉, 시작 노드가 빨간색이다. 

여기서 파란색 노드는 빨간색 노드만 거쳐서 가는 길이므로, 바로 연결된 두 노드는 각 15, 19가 되고

만약 이 파란색 노드와 연결된 곳은 shortest path가 없는 것이기 때문에 ∞로 생각할 수 있다.

 

proof

base

맨 초기에 해당 조건들을 만족한다. 

파란색은 red만 지나서 갈 수 있는 path이고 빨간색은, shortest path이다.

 

step

루프를 한번 도는 동안 while에 있는 조건을 만족할 수 있는지 확인해야함.

이미 빨간색 부분이 증명되었다고 가정하고, 다음 단계를 증명하면 된다. 

파란 숫자 : 빨간 노드들만 거쳐가는 가장 짧은 길의 길이 

* 이때 어떤 엣지를 거쳐서 가는지는 고려하지 않아도 됨. 아무튼 가장 짧은 길이임. 또한, 그냥 알고 있다고 "믿는" 것

 

while을 따라가보자

blue들 중에 가장 짧은 것을 찾자 smallest \(d_{min}(u)\) that not in R ( Greedy )

그림으로 보면 15이다. 따라서 15를 Red에 포함시킨다.

파란 숫자들 중 가장 작은 값은 곧 "정답"이다. 

 

Q) 밖에 있는 것 중 (파란 숫자들 중) 가장 작은게 정답인 이유

A) 만약, 15가 정답이 아니라면, 15보다 더 좋은 것이 있는것이다. 

먼저, 빨간 것만 거쳐서 오는 것이 15보다 더 좋을 수 없다. 왜냐면, 이미 빨간것만 거쳐서 오는 것 중 가장 좋은 것이 15이기 때문이다.

그러면 15보다 더 좋은게 있으려면 무조건 파란것을 거쳐서 와야하는데, 다른 것은 이미 15보다 크기 때문에 무조건 15보보다 좋을 수 없다.

 

따라서 R <- R \(\cup\) {u} 까지 진행하였다. 

따라서 지금 R이 업데이트 했기 때문에, 파란색을 업데이트 해야한다. 

원래 새로 추가된 15를 사용하지 않고 17에 갈 수 있었는데, 15를 사용해서 더 좋은 길로 갈 수 있다면 이를 사용해야함.

새로 R에 들어간 node를 u, 그리고 밖에 업데이트해야하는 노드를 w라고 하자.

 

원래 알던 길이와 u까지 오는 edge에 w로 바로 가는 edge의 weight를 더한 값을 비교하여 더 작은 숫자를 선택한다. 

 

Q) 왜 다른 길로 가는 것을 따지지 않아도 되는가?

A)세가지 경우를 생각해보자

1. u -> ..... -> w

2. u -> w

3. u->v(u이전의 red 집합)->w인 경우는 따지지 않는다. 

1번을 확인해보자. 만약 w 전에 있는 ... 들이 shortest path라면, w가 red 에 들어가기 전에 다른 것들이 먼저 들어가기에 상관이 없다.

3번을 확인해보자 . v가 빨간 집합에 추가되는 시점에 보면, u는 밖에 있다. 따라서 v의 shortest path 중에 u를 거치지 않아도 shortest path인게 있으므로, 3번은 u 없이도 이미 고려가 된다. 이미 있던 값 17에 반영이 되어있는 것과 같다. 

(u->v)가 shortest path라고 하더라도 상관 없다.

 

Find Actual Path

base

source와 source에서 바로 오는 것들이 파란 집합이므로 path를 알고 있다.

즉, 본인에서 바로 앞에 있는 path를 안다면, 그 전에껄 계속 따라가면 되기 때문에 바로 앞이 어떤 노드인지 알면 된다. 

step

w는 shortest path가 어떤 노드를 통해서 오는지 알고 있다고 가정하자

u가 추가된 이후, w는 원래 오는것이 좋은지 u를 통해 오는 것이 좋은지 비교한다.

그러면 w는 원래 오던 길이 좋다면, 원래 오던 길을 기억하고

아니라면 u를 통해서 온다는 것을 기억한다.

 

이를 계속 기억하면 이는 Tree 구조를 만든다. 

-> Shortest path Tree

source를 root로 하는 트리가 만들어진다.

 

Find All Paths

모든 경로를 기억한다고 하자.

에를 들어 같은 길이가 두개라고 생각하면, 그냥 나에게로 오는 바로 직전의 길을 기억하면된다. 

중간에 두개를 기억하는 노드가 존재할 수 있는 것이다. 

각자는 자기 앞의 노드만 기억한다. 

Directed graph (no cycle)이다.

-> Shortest Path DAG

 

Implementation

G = (V,E)가 있고 |v| = n, |E| = m

For u ∈ V do \(d_{min}(v)\) <- g(\(v_0\), u) : O(n) 시간

source를 Red에 넣는 것 : O(1) 시간

while n번 함 

> blue인 얘들 중 가장 작은 것을 구하는 것 (priority queue를 사용함) : O(log n)

> R에 추가하는 것 : O(1)

> u와 인접한 노드들 w를 따져 \(d_{min}(w)\) 업데이트 : O(log n)

> Blue에 추가하는 것 : O(1)

전체 시간 O(m log n)