다익스트라 알고리즘의 증명

알고리즘에 대한 설명은 생략하겠다.

이 글에서는 다익스트라 알고리즘의 증명만, 그것도 최대한 간단하게 설명할 것이다.

증명은 귀류법으로 진행된다.

 

---

 

1.

다익스트라 알고리즘이 정당하다면, 한번 결정된 최단거리가 갱신되는 일은 없어야 한다. 만약 갱신된다면 그것은 '진짜' 최단거리가 아니기 때문이다.

 

2.

증명을 위해, 다익스트라 알고리즘이 정당하지 않다고 가정하자. 이는 최단거리가 갱신될 수 있다는 뜻이다.

 

3.

다익스트라 알고리즘에 의하면, 한 노드의 최단거리가 결정되는 시점은 해당 노드를 방문할 때가 된다. 따라서 최단거리의 갱신은 그 이후에, 즉 아직 방문하지 않은 노드에 의해서만 이루어질 수 있다.

 

4.

그러나 이는 불가능하다. 다익스트라 알고리즘은 매 반복마다 가장 가까운 노드를 방문하는데, 어떻게 아직 방문하지 않은 노드가 더 가까울 수가 있고, 또 그것으로부터의 가중치를 더한 값이 더 작을 수가 있을까?

 

5.

따라서 우리는 가정이 잘못되었음을 알 수 있고, 다익스트라의 정당성을 입증할 수 있다.

 

---

 

증명이 간단한 만큼 배경지식이 부족하다면 이해하기 어려울 수도 있다.

참고로, 4번 과정은 왜 다익스트라 알고리즘이 음수 간선을 수용할 수 없는지를 보여주기도 한다.