[알고리즘] III-1. 다익스트라 알고리즘 (Dijkstra Algorithm) 이해하기

1.  탄생 배경

이 알고리즘의 저자인 다익스트라는 1956년 암스테르담에서 ARMAC이라는 새로운 컴퓨터의 성능을 보여주기 위한 적절한 주제를 고민하고 있었다고 한다. 그러던 어느 날 오전에 쇼핑을 하던 중 지쳐서 카페에서 커피를 마시다가 최단 경로 탐색 법을 고민하게 되었고 이 알고리즘을 약 20분(...!) 만에 완성했다고 한다.

2. 이해하기: 다익스트라 알고리즘

2-1. 기본 로직

다익스트라 알고리즘은 하나의 시작점에서 다른 모든 점들까지의 최단 경로를 구한다.

어떠한 원리로 최단 경로를 찾아가는지 직관적으로 이해를 돕기 위해 아래의 예시처럼 가장 기초적인 그래프부터 살펴보겠다.

 

 

 

 

 

 

1) 첫 단계는 현재 노드를 기준으로 나머지 노드들까지의 거리를 계산을 하는 것이다.

   인접해 있는 노드들은 해당 거리(edge의 weight)를 적어주고, 인접해 있지 않는다면 모르기 때문에 ∞로 적는다.

 

 

 

 

 

2) 현재 노드를 제외하고 나머지 노드들 중 가장 작은 거리를 가지고 있는 노드를 선택한다.

   

 

 

 

 

 

그 후, 선택한 노드를 기준으로 인접한 노드들의 최단 거리를 계산한다. 만약 기존에 가지고 있던 거리보다 더 작다면, 대체한다.

 

 

 

 

 

 

이 2) 과정처럼 현재 위치를 기준으로 다음 노드로의 최단 거리를 계산하는 방법을 완화(relaxation)이라 한다.

이 완화 과정이 다익스트라의 핵심인데, 완화를 수식적으로 정리하면 다음과 같이 설명할 수 있다.

 

 

 

 

2-2. 직관적으로 이해하기

앞에서 했던 과정을 모든 노드에 대해 반복하면 결국 최단거리 경로를 찾게 된다. 그대로 다음의 그래프에 적용시켜보자.

 

 

 

 

 

 

 

 

 

 

 

 

 

현재 노드 기준으로 인접해 있는 노드는 거리를 저장하고, 나머지는 ∞으로 저장한다.

 

 

 

 

 

 

 

 

 

 

 

이렇게 다익스트라 알고리즘이 어떠한 원리로 작동하는지 직관적으로 이해해보았다. 

다음 글에선 실제 코드에서 이러한 기본 원리가 힙 자료구조를 통해 구현되는 과정을 알아보겠다.