[CS기초] 다익스트라 알고리즘(Dijkstra's Algorithm)

다익스트라 알고리즘

다익스트라 알고리즘 개요

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘인데요. 다만 이 알고리즘을 사용하기 위해서는 모든 간선의 가중치가 0 이상이어야 하며, 음의 간선이 존재하면 사용할 수 없습니다.

 

 

다익스트라 알고리즘의 특징

다익스트라 알고리즘은 매번 가장 비용이 적은 노드를 선택하면서 진행되므로, 기본적으로 그리디(Greedy) 알고리즘으로 분류됩니다.

 

동작 과정은 다음과 같습니다.

1. 출발 노드를 설정한다.
2. 모든 노드에 대한 최단 거리 테이블을 초기화한다. - 출발 노드는 0, 나머지는 INF(무한대)
3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 인접한 노드로 가는 비용을 계산하여, 현재 저장된 최단 거리보다 작으면 갱신한다.
5. 3~4번 과정을 모든 노드를 방문할 때까지 반복한다.

이처럼 다익스트라 알고리즘은 각 노드에 대한 최단 거리 정보를 테이블 형태로 유지하면서, 더 짧은 경로가 발견되면 그 값을 갱신해 나갑니다.

 

 

다익스트라 알고리즘의 핵심 아이디어

다익스트라 알고리즘은 현재까지 발견된 최단 거리 정보를 바탕으로, 다음으로 탐색할 노드를 선택하고 해당 노드를 기준으로 인접 노드들을 갱신하는 방식으로 동작합니다.

 

즉,

• 아직 방문하지 않은 노드 중에서,
• 현재까지의 최단 거리가 가장 짧은 노드를 선택하고,
• 그 노드를 거쳐 다른 노드로 가는 경로가 더 짧다면 최단 거리 테이블을 갱신하는 것입니다.

 

다익스트라 알고리즘의 시간 복잡도

다익스트라 알고리즘은 노드를 선택하는 과정에서 힙(우선순위 큐)을 사용하면 효율적으로 동작할 수 있는데요. 이 경우 정점(V)과 간선(E)에 대해 시간 복잡도는 O(ElogV)가 됩니다.

 

이는 힙을 통해 가장 짧은 거리의 노드를 빠르게 찾을 수 있기 때문에 가능한 시간 복잡도인 것이죠.

 

 

파이썬에서 다익스트라 알고리즘의 구현

import heapq
INF = int(1e9)  # 무한을 의미하는 값 10억 설정

# 노드 개수, 간선 개수 입력
v, e = map(int, input().split())
# 시작 노드 번호 입력
start = int(input())
# 각 노드의 인접 노드 정보를 담는 리스트
graph = [[] for _ in range(v+1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (v+1)

# 모든 간선 정보 입력
for _ in range(e):
    # a 노드에서 b 노드로 가는 데 비용 c가 든다는 의미
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로 0으로 설정 및 큐 삽입
    distance[start] = 0
    heapq.heappush(q, (0, start))
    while q:    # 큐가 빌 때까지
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
        if dist > distance[now]:
            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, v + 1):
	# 도달할 수 없는 경우, 무한(INFINITY)을 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])