[알고리즘] 다익스트라 알고리즘

다익스트라(dijkstra) 알고리즘은 일상생활에서, 지하철, 내비게이션 등 여러 분야에서 사용되는 알고리즘이다. 활용 예시를 보면 알 수 있듯이 최단 경로 알고리즘인 다익스트라 알고리즘을 알아보자.

 

 

 

 

# 다익스트라 알고리즘

• 하나의 시작 정점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘
• 자료 구조로는 그래프(graph) 사용
• 노드와 가중치를 가진 간선을 이용하여 실제 거리를 표시한다.
• 초기에 우선순위 큐를 사용하지 않은 다익스트라 알고리즘 O(V^2)의 시간 복잡도
• 우선순위 큐로 인한 개선으로 O(E log V) - V, E = 노드와 간선의 수
• 삽입 삭제, 최소 값 추출 - O(logV)
• 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 사용 => 다이나믹 프로그래밍의 특징과 동일
• 또한 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사

 

단점

 

• 다만, 양의 정수인 그래프에서만 사용 가능
• 기본적으로 Greedy 탐색이므로, 비용 감소, 이득이 되는 경우 고려 xx
• 당장의 비용이 최소라면, 그 길을 택함
• 즉, 멀리 돌아서 가는 경우가 비용이 적게 들어도 다익스트라로는 고려할 수 없다.

 

 

알고리즘 구현

 

# HEAPQ 이용 - O(N*logN)

 

1. 시작노드(start라고 하자)에 대해서 방문처리 및 인접 노드의 최단 거리를 갱신한다.
2. 방문처리가 안된 노드 중 최단 거리가 가장 짧은 노드(now라고 하자)를 선택하고 방문처리해준다.
3. 시작 노드(start)로부터 해당 노드(now)를 거쳐 해당 노드의 인접한 노드까지의 거리와 기존의 distance에 저장되어 있는 시작 노드부터 해당 노드와 인접한 노드의 거리를 비교하여 최솟값을 갱신해준다.

# 다익스트라 알고리즘
# 간선 길이가 양의 정수인 그래프에서 최단 거리를 계산
# 간선 길이를 고려하여 노드에 순위를 매기고자 일반적인 큐 대신에 우선순위 큐를 사용하는 것을 말고는 BFS와 같다.
# 시간 복잡도는 우선순위 큐 구현 방법에 달려있다. 이진 히프(O((V+E)logV), 삽입, 삭제 logV, 최소값 추출 logV
# 다익스트라 알고리즘은 시작점부터 가장 가까운 노드를 포함한 그래프를 생성하고, 그래프 밖에 있는 가장 가까운 노드를 그래프에 포함하는 것으로 생각할 수 있다.
# 정점의 거리 update의 연속으로 볼 수 있다.

import collections
import sys
import heapq

input = sys.stdin.readline

V, E = map(int, input().split()) # 정점, 간선 수 입력 받기
graph = collections.defaultdict(list) # 빈 그래프 생성

for _ in range(V):
    u, v, w = map(int, input().split())
    graph[u].append(v,w) # 그래프 생성

# 다익스트라 알고리즘
def dijkstra(graph, start):
    Q = [(0, start)] # 우선순위 큐생성 (거리, 정점)
    distance = collections.defaultdict(int) # 거리 정보를 담을 자료구조 생성

    while Q:
        dist, node = heapq.heappop(Q) # 힙 추출
        if node not in distance: # 방문한 노드가 아니면 거리 정보 저장
            distance[node] = dist
            for v, w in graph[node]: # 인점 노드 탐색
                update = dist + w # 거리 정보 갱신
                heapq.heappush(Q, (Q, (update, v))) # 우선 순위 큐에 삽입

    # 최단 경로 존재 여부 판별, distance 수가 전체 정점 수와 같은지 확인
    if len(distance) == V:
        return max(distance.values()) # 최단 거리 추출
    return -1 # 최단 거리가 없으면 -1 반환

 

 

 

# bfs 이용하여 구현 -  O(N^2)

 

• 거리를 저장할 배열을 만들어 준 후 인접한 미방문 노드를 q에 넣어준 후 탐색
• 값에 따라 갱신해주며 도착지점까지 계산해주면 된다.

import sys
input = sys.stdin.readline

V, E = map(int, input().split())
S = int(input())
INF = 10000000
# 인접 노드를 저장하는 배열
graph = [[] for _ in range(V+1)]
# 노드 방문 여부
visited = [False]*(V+1)
# 최단 거리 저장하는 배열
distance = [INF]*(V+1)

for _ in range(E):
    U, E, W = map(int, input().split())
    graph[U].append((E, W))

# 방문 처리가 안된 노드 중 가장 최단 거리가 짧은 노드를 찾는 함수
def get_smallest_node():
    min_value = INF
    temp_index = 0
    for i in range(V+1):
        if visited[i] == False and min_value > distance[i]:
            min_value = distance[i]
            temp_index = i
    return temp_index

# 다익스트라 알고리즘을 실행하는 함수
def dijsktra(start):
    distance[start] = 0
    visited[start] = True
    # start노드에 인접한 노드들의 최단거리 갱신
    for i in graph[start]:
        distance[i[0]] =i[1]
    
    # 시작 노드를 제외한 V-1개의 노드를 방문해야 하므로 V-1번 반복
    for _ in range(V-1):
        # 최단 거리가 가장 작은 노드를 now에 저장
        now = get_smallest_node()
        # 방문처리
        visited[now] = True
        # now에 인접한 노드들을 돌면서 최단 거리 갱신
        for i in graph[now]:
            if distance[i[0]] > distance[now] + i[1]:
                distance[i[0]] = distance[now] + i[1]

dijsktra(S)

for i in range(1, V+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])