[알고리즘] Dijkstra's algorithm 1부 - 이론

💡 Introduction
다익스트라 알고리즘 (Dijkstra's algorithm) 은 탐욕법 (Greedy) 의 대표적인 응용 알고리즘이다.
이번 포스트에서는 다익스트라를 예시 그래프를 통해 설명하고, 다음 포스트와 그 다음 포스트를 이용해 직접 코드로 구현해본다.

🔍 다익스트라 알고리즘이란?

다익스트라 알고리즘은 가중 그래프 (Weighted Graph, 정점간의 거리가 나타나 있는 그래프) 에서 각 정점까지의 최단 거리를 찾아낼 수 있는 알고리즘이다. 바로 예시를 통해 설명하도록 하겠다.

 

📃 다익스트라 알고리즘 예시

먼저, 아래 사진의 왼쪽에 놓여진 것과 같은 그래프가 있다고 하자. 이 그래프를 분석하여 오른쪽 표에 쓰여진 두 종류의 정보를 파악할 수 있다. A 가 시작점일 때, A 는 자기 자신까지의 거리이므로 시작점으로부터의 거리가 0이고, 나머지 정점까지의 거리는 아직 알지 못하기 때문에 극한 값(∞) 을 가진다. 거리 외에도 방문한 / 방문하지 않은 정점들의 목록 visited / unvisited 와 현재 방문 중인 정점 current 를 추적한다.

왼쪽에 그려진 것은 예시 그래프이다. 다익스트라는 오른쪽 표로 나타낸 두 종류의 데이터를 추적하여 활용한다.

 

1번 단계는 아직 방문하지 않은 정점들 중 시작점에서 가장 가까운 정점을 방문하는 단계이다.

처음에는 A가 거리 0 을 갖고 있기 때문에 가장 가깝다.

A 를 방문했다. 현 상태에 따라 표 내용도 업데이트되는 것을 볼 수 있다.

 

2번 단계는 현재 방문 중인 정점에서 아직 방문되지 않은 이웃 정점들까지의 거리를 확인하여 만약 현재까지 알려진 거리보다 작을 시에만 업데이트하는 단계이다. 지금은 모두 무한대(∞) 보다는 가까운 거리이므로 모두 업데이트한다.

거리는 시작점으로부터 현재 방문하는 중인 정점까지의 거리 +  현재 방문중인 정점부터 이웃까지의 거리이다.

B 와 C 의 시작점으로부터의 거리가 업데이트되었다. 각각 0 + 3 = 3 과 0 + 5 = 5 로 업데이트 되었다.

 

그 다음부터는 1번과 2번 단계를 반복한다.

1번 단계인 아직 방문하지 않은 정점 중 가장 가까운 정점을 방문하는 단계를 반복한다. 현재는 B 이다.

그리고 2번 단계인 방문한 정점의 아직 방문되지 않은 이웃들의 시작점으로부터의 거리를 업데이트한다.

위에서 설명했듯이 현재 방문중인 B 까지의 거리 3 + B 부터 D 까지의 거리 4 = 7 로 업데이트된다.

7은 무한대(∞) 보다 작으므로 업데이트 되는 것이다.

현재 B의 이웃 중 방문되지 않은 정점은 D 이므로 D의 거리를 업데이트 했다.

 

1번과 2번을 한 번씩 거쳤으니, 또 1번 단계로 와서 방문하지 않은 정점들 중 가장 가까운 정점을 방문한다.

시작점으로부터 B 다음으로 가까운 정점인 C 를 방문했다.

 

2번 단계를 진행한다. 이웃들 중 방문되지 않은 정점까지의 시작점으로부터의 거리를 업데이트하거나, 만약 지금까지 알려진 거리가 이미 더 작다면 업데이트 하지 않는다. 여기서는 이미 알려진 거리인 7이 새롭게 알게 된 거리 12보다 작아서 업데이트가 진행되지 않는다.

시작점 A 부터 C 를 거쳐 D 까지의 거리는 5 + 7 = 12 이다. 지금까지 알려진 거리보다 더 짧지가 않아서 의미가 없다.

 

또 1번 단계를 반복한다. 마지막 남은 방문하지 않은 정점인 D 를 방문한다.

이제서야 D 에 도달했다.

 

2번 단계를 진행하려고 하는데, 이웃들은 모두 이미 방문했어서 거리를 파악해야 할 정점이 존재하지 않는다.

전체에서 봤는데 이제는 방문하지 않은 정점이 없다. 탐색을 종료한다.

탐색을 종료할 때의 상태이다. visited 에 모든 정점들이 들어가있고, 모든 정점들에 대해서 시작점으로부터의 최단 거리를 찾았다.

 

📌 결론

이렇게 다익스트라 알고리즘을 활용하여 원래 목표했던 더 이상 앞으로 갈 길이 없는 마지막 정점, D 까지의 거리 뿐만 아니라 모든 정점까지의 최단 거리를 구할 수 있었다. 다음 포스트에서는 다익스트라 알고리즘을 구현할 준비를 해보자.

 

출처

https://www.linkedin.com/learning/algorithmic-thinking-with-python-foundations/dijkstra-s-algorithm?autoplay=true&resume=false&u=62535084 

Dijkstra's algorithm - Python 동영상 튜토리얼 | LinkedIn 온라인클래스(이전 이름: Lynda.com)