알고리즘6 Djikstra Algorithm

Djikstra Algorithm

유명한 Shortest Path의 정답. 프림 알고리즘과 유사하다.

시작은 한군데지만 모든 목적지로 가는 shortest path를 다 구한다.

shortest path의 모든 부분은 shortest path이다.

 

 

대부분 path를 구하는 것이 아니라 path의 길이만을 구한다.

=> 길까지 구하는 것으로 금방 바꿀 수 있다. 심지어 path가 여러 개일때 모든 path를 다 찾을 수 있다.

 

3단계로 나눠서 얘기하면 이를 설명할 수 있음

일단 1단계부터 설명 => 2단계로 바꾸고 => 3단계로 바꿀 것임

 

 

(1단계에서 왜 이게 답을 찾느냐가 어려움)

---

 

 

 

G: 입력 그래프

n: 노드 갯수

R: 빨간 노드 집합

V0: source node

dmin: 노드에 써진 숫자

 

빨간노드와 파란 노드가 있다.

빨간 노드:  최종 정답을 아는 노드 , 빨간 숫자를 가지고 있다.

빨간 숫자: 최종 정답

파란 노드: 최종 정답을 모르는 노드, 파란 숫자를 가지고 있다.

파란 숫자: Red node들만을 거쳐서 올 수 있는 가장 짧은 길의 길이

 

T: 빨간 노드들의 집합

T가 아닌 애들은 파란 노드

 

 

 

 

시작했을 때 source node는 본인이 0이라는 것을 알고 있다. (유일한 레드 노드)

오른쪽 위의 노드는 source node에서 빨간 것만 거쳐서 갈 수 있는 가장 짧은 길이 없다.

엣지가 없으므로 무한대라고 생각 (그래프의 모든 엣지를 다 더한 것보다 큰값..일단 무한대로 써놓기)

 

파란 노드 2개는 빨간 노드만을 거쳐서 갈 수 있는 가장 짧은 길의 길이 = 15, 19이므로

각각의 엣지의 weight는 15, 19이다.

(바로 가는 것이 답이 아니므로 파란 숫자로 써야 한다.)

 

 

한 바퀴 돌때마다 빨간 노드가 하나씩 추가된다.

간단한 그리디 작전! (이 작전이 왜 통하느냐가 중요)

파란노드들 중에 dmin이 가장 작은 걸 찾아라

 

---

※ 파란 노드가 빨간 노드를 전부 다 지나야 하는 것은 아님 = 파란 노드는 파란 노드를 못 거친다.

 

지금까지 재귀적으로 정상적으로 동작했다고 생각하며, 빨간 노드 하나를 더 추가시키면 되는 상황

 

다익스트라 알고리즘의 주장 : 파란 노드 중에 가장 작은 것은 정답이다 (15가 정답이라고 주장)

파란 노드 중 15가 제일 작으니까 빨간 노드로 바꾼다.

 

이유: (밑에 이해 안감 ㅠㅠ 어려워)

 

우리가 15노드에 대해 알고 있는 2가지 fact

1. 15는 빨간 것만 거쳐서 오는 제일 짧은 거리이다

2. 파란 숫자 중 가장 작은 값이 15이다.

 

다익스트라 알고리즘은 파란 노드 중 가장 작은 15를 정답이라고 생각하고 빨간 노드로 바꿔버린다. 

(아직 사실인지 모르지만 다익스트라 알고리즘의 주장)

 

 

그래서 그 주장을 어떻게 확인하는데?

그 주장이 틀렸다면 어떻게 될지를 생각해보자

 

 

팩트: 빨간 노드만 거쳐서 오는 것 중에 가장 짧은 값은 15이다.

만약 15가 정답이 아니라면? 더 좋은 답이 있다면?

그 답은 빨간 노드만을 거쳐서 오는 것이 아닐 것이다. 

왜냐하면 빨간 노드만 거쳐서 오는 것 중에 가장 짧은 값은 15이기 떄문에

그건 파란 노드를 거쳐서 오는 것일 것임

 

파란 노드를 거치는 path가 있다면 그 중 빨간 것만 거쳐서 최초로 파란 노드로 나오는 순간이 있을 것이다.

그리고 그것이 15보다 작아야 하는데 이미 15는 빨간 것만 거치는 노드 중 가장 작은 값이기 때문에 불가능

 

ex

(20노드에 도달하기 전에 최초의 파란 노드가 있었다면 그 값은 20보다 작을 것임. 하지만 15보단 클 것이기 때문에 X)