[알고리즘] 데이크스트라 최단 경로 알고리즘

데이크스트라 알고리즘 (Dijkstra Algorithm)

 

최단 경로 알고리즘은 주어진 그래프에서 가장 빨리 도달할 수 있는 길을 찾는 알고리즘이다. 노드를 연결하는 간선에 비용 있어 간선의 갯수가 같다고 하여도 실제 이동시간은 다를 수 있기에 그런 것들을 잘 체크해주어야 한다.

 

데이크스트라 알고리즘은 음의 간선이 없을 때 정상적으로 작동한다. 음의 간선이란 0보다 작은 값을 가지는 간선을 의미하는데, 현실 세계에서 음의 간선이란 존재할 수 없다. 때문에 GPS 소프트웨어의 기본 알고리즘으로 채택되기도 한다.

 

데이크스트라 알고리즘의 동작 원리는 인접한 노드중에 가장 비용이 적은 노드를 선택하여 움직이기에 그리디 알고리즘으로 분류된다.

 

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화 한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 위 과정에서 3과 4번을 반복한다.

최단 거리 테이블을 초기화 할 때는 1차원 배열에 노드의 갯수만큼 무한으로 초기화 한다.

 

 

다음과 같은 그래프가 있다고 가정해보자.

노드는 1부터 6까지 있다.

출발 노드는 1이라 하겠다. 데이크스트라 알고리즘은 출발 노드에서 모든 노드의 최단 경로를 알려준다.

앞서 설명한 것처럼 초기 테이블은 시작노드를 제외하고 무한으로 초기화 한다.

 

노드 번호	1	2	3	4	5	6
거리	0	무한	무한	무한	무한	무한

 

STEP 1: 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하는데, 출발 노드에서 출발 노드로의 거리는 0으로 보기 때문에 처음에는 출발 노드가 선택된다.

 

1번 노드와 이웃한 노드는 2,3,4 노드이고, 각각 비용이 2(0+2), 5(0+5), 1(0+1)이다. 모두 무한보다 작으니 새로 갱신한다.

 

노드 번호	1	2	3	4	5	6
거리	0	2	5	1	무한	무한

STEP 2: 스텝 2에서는 4번 노드를 탐색한다. 4번 노드에서는 3번노드를 4(1+3), 5번 노드를 2(1+1)에 갈 수 있고, 이 두 값은 기존의 리스트에 담겨 있던 값보다 작으므로 다음처럼 리스트가 갱신된다.

 

노드 번호	1	2	3	4	5	6
거리	0	2	4	1	2	무한

 

STEP 3: 스텝 3에서는 2번 노드가 선택된다. 그러나 2번 노드를 거쳐 가는 경로중에 최단 거리를 더 짧게 갱신할 수 있는 방법은 없다.

 

STEP 4: 스텝 4에서는 5번 노드가 선택되고 3번 노드와 6번 노드가 갱신된다.

노드 번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

 

STEP 5: 3번 노드가 선택된다.

 

STEP 6: 6번 노드가 선택된다.

 

이런 식으로 방문하지 않은 노드 중 가장 작은 순으로 방문을 해나가며 테이블을 갱신하는 것이 데이크스트라 알고리즘이다.

 

최종 테이블은 아래와 같다.

노드 번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

 

1번 노드에서 2번 노드까지의 최단 경로는 2, 1번 노드에서 3번 노드까지의 최단 경로는 3... 이런 식으로 해석하면 된다.

 

코드로 구현한 간단한 데이크스트라 알고리즘 소스코드는 다음과 같다. 시간복잡도는 O(N**2)이다. 이유는 단계마다 "방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 리스트의 모든 원소를 리니어 적으로 확인하기 때문이다.

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
 
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 방문한 적이 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (n + 1)
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)
 
# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b, c))
 
# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
    min_value = INF
    index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
    for i in range(1, n + 1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index
 
def dijkstra(start):
    # 시작 노드에 대해서 초기화
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]
    # 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
    for i in range(n - 1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
        now = get_smallest_node()
        visited[now] = True
        # 현재 노드와 연결된 다른 노드를 확인
        for j in graph[now]:
            cost = distance[now] + j[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[j[0]]:
                distance[j[0]] = cost
 
# 다익스트라 알고리즘을 수행
dijkstra(start)
 
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

출처 이것이 코딩 테스트다

 

개선된 데이크스트라 알고리즘은 우선순위 큐를 사용하여 가장 가까운 노드를 찾는데 시간복잡도를 O(ElogV) 로 줄일수 있다. (이때 E는 간선 V는 노드의 개수)

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
 
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)
 
# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b, c))
 
def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q: # 큐가 비어있지 않다면
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if distance[now] < dist:
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
 
# 다익스트라 알고리즘을 수행
dijkstra(start)
 
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])
        
# 출처: https://github.com/ndb796/python-for-coding-test/blob/master/10/3.py

 

앞으로 최단경로 문제가 나오면 데이크스트라 알고리즘을 사용해보자!!!

단 주의해야할 점은 음의 간선이 없어야 한다는 것이다.

 

추가로 현재 우리가 지하철 노선도에서 사용하는 길찾기 기능은 이 데이크스트라 알고리즘을 사용한다.