다익스트라 알고리즘을 이해하기 위해 개념/이론적인 부분과 코드구현 부분을 나누어서 설명하고자 한다.
이론 이해하기
- 다익스트라 알고리즘 : 그래프에서 하나의 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘
- 조건 : 모든 간선(edge)의 가중치/비용(weight/cost)은 양의 정수값이어야 한다.
- 대표적인 최단경로 알고리즘 : Dijkstra 알고리즘, Bellman-Ford 알고리즘, Floyd-Warshall 알고리즘
최단경로 문제를 풀 때, 경로 계산하는 방식은 유형이 나뉩니다. 그 중에 다익스트라 알고리즘은 유형1입니다.
유형1. 한 노드에서 다른 모든 노드까지의 최단경로 구하기
유형2. 한 노드에서 다른 특정 노드까지의 최단경로 구하기
유형3. 모든 노드에서 모든 노드까지의 최단경로 구하기
다익스트라 알고리즘은 과정을 반복한다.
Step1. 방문하지 않은 노드 중 가장 가중치가 낮은 노드를 방문한다
Step2. 해당 노드를 방문해서 갈 수 있는 노드의 거리가 이전의 기록한 값보다 작다면 그 거리를 갱신한다.
작은 그래프를 이용한 간단한 예시부터 큰 그래프의 예시를 확인해보면 이해하기 쉽다.
아래와 같은 그래프에서 시작정점은 Node 0이라고 가정하고 나머지 정점까지의 최단거리를 계산해보자. Node 0부터 다른 Node까지의 거리를 나타내는 테이블의 초기값은 INF(Infinity, 무한대)로 설정한다.
- 시작점인 Node 0을 방문
- Node 0과 연결된 간선(Edge)를 이용해서 거리값을 나타내는 테이블을 업데이트
- 방문한 Node 0은 "방문했음(Visited)"을 체크
- 방문하지 않은 점중에 거리가 가장 가까운 Node 2를 방문
- Node 0에서 Node 2를 지남으로써 줄어들게 되는 거리를 갱신한다
- Node 0 → Node 2 → Node 3의 거리값이 Node 0 → Node 3보다 작으므로 갱신한다(8 →5)
- Node 0 → Node 2 → Node 4의 거리값이 Node 4로 가기위한 값이므로 갱신한다(INF→10)
- 방문하지 않은 점중에 거리가 가장 가까운 Node 1를 방문
- Node 1을 지남으로써 줄어들게 되는 거리를 갱신한다
- Node 0 → Node 1 → Node 4의 거리값이 Node 0 → Node 2 → Node 4 보다 작으므로 갱신한다(10 → 9)
- 방문하지 않은 점중에 거리가 가장 가까운 Node 3를 방문
- Node 3을 지남으로써 줄어들게 되는 경우가 없으므로 갱신할 부분은 없다.
- 방문하지 않은 점중에 거리가 가장 가까운 Node 4를 방문
- Node 4을 지남으로써 줄어들게 되는 경우가 없으므로 갱신할 부분은 없다.
- 모든 정점을 방문했으므로 종료한다.
위 과정을 통해서 Node 0 기준의 최단거리 테이블이 완성되었다.
Dijkstra 알고리즘을 구현하는 방식을 크게 1) 선형 탐색 방식(기본)과 2) Heapq 방식 2가지가 있다. 다음글에서 코드기준의 구현을 보면서 시간복잡도에 대해서도 알아보자.