Dijkstra 알고리즘을 이해하려면, 먼저 최단 경로의 성질을 이해해야 한다.

이 성질에 대해서 알아본 다음에 Dijkstra 알고리즘으로 구한 경로가 왜 최단 경로인지 알아보자.

 

최단 경로 문제와 최적 부분 구조(Optimal Substructure)

---

Dijkstra 로 구한 경로가 왜 최단 경로인지 보기 전에 먼저 최단 경로의 중요한 성질 하나를 짚고 넘어가자.

 

위 그래프를 보면, A 에서 E 까지의 최단 경로는 A - C - D - E 이다.

여기서 부분 경로를 보자, 부분 경로는 그냥 경로 안에 있는 경로이다.

예를 들어 A - C - D C - D - E 이런 건 다 A - C - D - E 안에 있는 경로들이다.

이런 걸 부분 경로라고 한다.

 

자, 여기서 특별한 성질 하나를 알려주겠다.

만약 A - C - D - E 가 A 에서 E 까지의 최단 경로라면, A - C - D 는 A 에서 D 까지의 최단 경로고, C - D - E 는 C 에서 E 까지의 최단 경로이다.

최단 경로 안에 있는 부분 경로들은 모두 최단 경로이다.

 

이것을 어떻게 증명할 수 있을까?

 

최단 경로 안에 있는 부분 경로들이 최단 경로가 아니라고 가정을 하자.

예를 들어서 A - C - D - E 가 A 에서 E까지의 최단 경로인데, A 에서 D 까지의 최단 경로가 A - C - D 가 아니라 A - B - D 라고 가정하는 것이다.

이게 말이 될까?

 

A - B - D 가 A - C - D 보다 더 짧다면, A 에서 D 까지의 최단 경로는 A - C - D - E 가 아니라 A - B - D - E 가 되어야 한다.

애초에 우리가 가정한 게 말이 안된다는 소리다.

최단 경로 안에 있는 부분 경로가 최단 경로가 아닌 건 말이 안 된다는 것이다.

그러니까 최단 경로 안에 있는 부분 경로는 무조건 최단 경로라고 확신할 수 있다.

 

그럼 이 성질은 무엇을 의미할까?

A 에서 E까지의 최단 경로를 찾는 문제는 A 에서 D까지의 최단 경로를 찾는 문제와도 연관이 있고, A 에서 B 까지의 최단 경로를 찾는 문제와도 연관이 있고, A 에서 C까지의 최단 경로를 찾는 문제와도 연관이 있는 것이다.

최단 경로를 구하기 위해서 부분 최단 경로를 이용할 수 있다는 것이다.

 

Dijkstra 알고리즘 증명

---

Dijsktra 알고리즘을 처음 시작할 때를 생각해 보자.

Node A 를 시작점으로 했다고 하자.

A 의 distance 는 0

predecessor 는 None 이다.

 

그 다음에는 A와 인접한 Node 들을 도는데, 이미 방문한 Node는 무시한다.

일단 B 와 C는 다 방문한 적이 없다. B 부터 보자.

엣지 (A, B)와 (A-C) 를 relax 해준다.

 

그 다음에 A 를 방문했다는 표시를 해주고, 방문하지 않은 Node 중 distance 가 가장 작은 C 를 가지고 온다.

여기서 말하지 않은 한 가지 정보가 있다.

바로 이때의 C의 distance 1은 A에서 C까지의 최단 경로 거리라고 확신할 수 있다.

A에서 C까지 가는 많은 경로가 있다.

어떻게 바로 한 번에 1이 최단 거리라는 것을 알 수 있을까?

 

A는 인접한 Node가 B와 C, 딱 2 개 밖에 없다.

그럼 A 에서 C로 가는 모든 경로는 A 에서 B를 지나가거나 A에서 C를 지나가거나, B 와 C 중 하나는 무조건 지나갈 수 밖에 없다.

엣지 (A, C) 는 1이다.

C 를 지나가는 경로는 일단은 1 인 것이다.

그럼 이번에는 A에서 시작해서 B 를 지나가는 경로들에 대해서 생각해보자.

예를 들어서 A - B - C, A - B - D - C 이런 경로들이 있다.

B 를 지나가는 모든 경로의 공통점은 엣지 (A, B) 를 지나간다는 점이다.

그런데 생각해보면 A 에서 C를 가는 경로가 이미 A 에서 B로 가는 경로보다 작다.

그러니까 A - B 의 거리가 이미 4 니까 B를 지나가는 다른 모든 경로는 기본적으로 현재 C 의 distance 보다는 클 수 밖에 없다는 것이다.

그렇기 때문에 바로 C의 distance 1이 A 에서 C까지 가는 모든 경로 중 최단 거리라고 확신할 수 있다.

 

이런식으로 Dijkstra 에서는 방문하지 않은 Node들중 distance가 가장 작은 Node를 고른다.

C 의 distance가 시작점에서 C까지의 최단 거리라고 확신할 수 있는 것이다.

이렇게 각 단계에서 distance가 가장 작은 Node는 이미 최단 거리를 저장하고 있다고 확신 할 수 있다.

 

좀 더 보자. C는 이미 최단 거리를 구했으니까, 이번에는 C의 엣지를 relax 해줄 것이다.

현재 남은 Node 들 중 distance 가 가장 작은 Node 가 D 가 되었다.

이때도 마찬가지로 D 의 distance 가 A 에서 D까지의 최단 거리라고 확신할 수 있다.

 

왜 그런지 보자.

D 까지 가는 경로 중 최단 경로가 될 수 있는 모든 경로들에 대해서 생각해보자.

D 는 인접한 Node C B E 가 있다.

그럼 D까지 가는 최단 거리는

1. C까지 가는 최단 거리 + 엣지 (C, D)의 가중치
2. B까지 가는 최단 거리 + 엣지 (B, D)의 가중치
3. E까지 가는 최단 거리 + 엣지 (E, D)의 가중치

이렇게 3 가지 가능성 밖에 없다.

 

지금까지 A 에서 D 까지의 최단 경로는 A - C - D 경로고, distance 는 2이다.

그러니까 위에 3가지 가능성을 살펴봤을 때 경우 1인데, 어떻게 나머지 2개의 경우들을 보지도 않고 지금 경로보다 더 길다고 확정 지을 수 있나?

 

증명을 위해 현재 찾은 경로보다 더 짧은 경로가 있다고 하자.

그리고 이게 B를 통해서 D를 오는 경로라고 하자. 그 말은 B까지 가는 최단 경로 거리 + 엣지 (B, D)의 가중치가 2 보다 작다는 말이다. 이건 말이 안된다.

만약 B 까지 2 보다 짧은 경로가 있었으면 B의 distance가 D보다 작아야 한다.

D 는 이미 최단 거리가 확정된 Node 를 제외하고 distance가 가장 작은 Node 를 선택한 Node 이다.

그러니까 B 까지 가는 최단 경로 중 거리가 D가 distance 인 2 보다 작은 경로가 없다고 확정 지을 수 있다.

 

정리

---

1. Dijkstra 알고리즘은 반복문을 돌면서 최단 경로를 이미 찾은 Node를 하나씩 찾는다.
   1. 처음에는 시작 Node의 최단 경로를 확정 지었고, 그 다음에는 C의 최단 경로를 확정 지었다.
2. 그리고 최단 경로를 이미 찾은 Node의 엣지들을 모두 relax 해줬다.
   1. 최단 경로는 다른 Node들까지의 최단 경로 + 현재 Node기 때문에, 이미 확정난 최단 경로들로 다른 Node들까지의 최단 거리 예상치(distance)를 구한다.
3. 매 단계에서 이 **distance**가 가장 작은 Node는 최단 거리를 이미 찾았다고 확신을 할 수 있다.
   1. Node D까지 가는 최단 거리는 이 세 가지 가능성 중 하나일 수밖에 없다. (최적 부분 구조)
      1. C까지 가는 최단 경로 거리 + 엣지 (C, D)의 가중치
      2. B까지 가는 최단 경로 거리 + 엣지 (B, D)의 가중치
      3. E까지 가는 최단 경로 거리 + 엣지 (E, D)의 가중치
   2. D가 선택됐다는 건 현재 찾은 경로 A - C - D 의 거리가 B까지 가는 최단 거리, E까지 가는 최단 거리보다 작기 때문이다. 그렇기 때문에 반복문이 한 번 실행될 때마다 **distance**가 가장 작은 Node가 최단 거리 Node라고 확신할 수 있죠.

0 0