다익스트라 알고리즘

• 다익스트라 알고리즘은 그래프 내의 한 노드에서 다른 노드까지의 최단 경로를 찾는 알고리즘이다.

• 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 최단 경로 탐색 알고리즘이다.

  → 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문에 작은 문제들이 큰 문제의 부분 집합에 속해 있고 매번 가장 비용이 적은 노드를 선택하여 반복한다.. 또한 하나의 최단 거리를 구할 때 이전에 사용했던 최단 거리 정보를 그대로 사용한다.

• 다익스트라 알고리즘은 특정한 하나의 노드에서 다른 노드으로 가는 최단 경로를 알려준다.

• 다익스트라 알고리즘은 음의 간선을 포함할 수 없지만 현실 세계에서는 음의 간선이 존재하지 않기 때문에 현실 세계에서 사용하기 매우 적합한 알고리즘 중 하나이다.

다익스트라 알고리즘 동작 원리

• 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인해서 더 짧은 경로를 찾으면 최단 거리 테이블인 1차원 리스트에 저장한다.

다익스트라 알고리즘 과정

1. 출발 노드를 설정하고 최단 거리 테이블을 초기화한다.
2. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. (선택한 노드는 방문 처리한다.)
3. 해당 노드를 거쳐 다른 노드로 넘어가는 거리를 계산해서 최단 거리 테이블을 업데이트 한다.
4. (2) ~ (3) 과정을 반복한다.

다익스트라 구현 코드

import collections
import sys
import heapq

input = sys.stdin.readline

V, E = map(int, input().split()) # 노드, 간선 수 입력 받기
graph = [[] for _ in range(n + 1)]

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) # 거리 정보를 담을 자료구조 생성
		distance = [INF] * (n + 1)

    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, [update, v]) # 우선 순위 큐에 삽입

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

• 위 코드는 노드 수와 간선 수를 입력하고 각 거리 정보를 입력하여 다익스트라 알고리즘을 구현하는 코드이다.
• 위 코드에서는 힙을 사용한다.
• 힙이 무엇이냐!
  • 힙은 priorityqueue를 구현하기 위해 사용하는 자료구조 중 하나이다.
  • 우선순위가 가장 높은 데이터를 먼저 삭제한다.
  • 물론 PriorityQueue도 존재하지만 일반적으로 heapq이 더 빠르다.

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

• 기본적으로 O(n^2)이다. 방문하지 않은 모든 노드를 순회하므로 기본적으로 O(n)이고, 그 노드을 고르는 과정 중에 리스트 내에 있는 간선들 중 최소 비용인 것을 순회 비교하며 고르는 과정에서 O(n)이 든다.