다익스트라 알고리즘(Dijkstra)

참고사이트 : 다익스트라 알고리즘
나무위키- 다익스트라 알고리즘
다익스트라 최단경로 with Python

다익스트라 알고리즘이란?

다익스트라 알고리즘은 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신 하는 알고리즘이다.

즉, 가장 적은 비용으로 빠르게 정답에 도달하는 경로를 찾아내는 문제에서 주로 사용한다.

그림으로 살펴 보자.

1.아직 확인되지 않은 거리는 전부 초기값을 무한으로 설정한다.

2.루프를 돌려 이웃 노드를 방문하고 거리를 계산한다.

3.각 경로의 비용을 누적으로 저장한다. 이때 저장한 값이 다른 경로와 비교했을 때 작으면 가장 작은 값으로 업데이트를 진행한다.

4.계속 반복 후 목표점까지의 최단 거리를 찾는다.

다익스트라 알고리즘 구현 방법

1. 순차탐색
시간복잡도 : O(n^2)- 일일이 노드를 확인하는 방법

import sys

input = sys.stdin.readline # 빠른 입력
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 방문 체크
visited = [False]*(n+1)
# 최단거리 테이블
distance = [INF]*(n+1)

# 노드 연결정보
graph = [[] for i in range(n+1)]

for _ in range(m):
  # a번노드에서 b번 노드로 가는 비용c
  a,b,c = map(int, input().split())
  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]

  # 모든 노드에 대해 반복
  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):
  # 도달할 수 없는 경우
  if distance[i] == INF:
    print("infinity")
  else:
    print(distance[i])

2. 최소 힙 이용

• (거리, 노드 번호) 순서대로 튜플 데이터를 구성해 우선순위 큐에 넣으면 거리 순으로 정렬되는 알고리즘

import heapq
import sys

input = sys.stdin.readline # 빠른 입력
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 최단거리 테이블
distance = [INF]*(n+1)

# 노드 연결정보
graph = [[] for i in range(n+1)]

for _ in range(m):
  # a번노드에서 b번 노드로 가는 비용c
  a,b,c = map(int, input().split())
  graph[a].append((b,c))

# 다익스트라 알고리즘(최소힙 이용))
def dijkstra(start):
  q=[]
  # 시작 노드
  heapq.heappush(q, (0,start))
  distance[start] = 0

  while q:
    # 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
    dist, now = heapq.heappop(q)

    # 이미 처리된 노드였다면 무시
    # 별도의 visited 테이블이 필요없이, 최단거리테이블을 이용해 방문여부 확인
    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):
  # 도달할 수 없는 경우
  if distance[i] == INF:
    print("infinity")
  else:
    print(distance[i])

다익스트라 알고리즘 특징

장점

• 인접 행렬 또는 우선순위 대기열을 사용하여 구현할 수 있으므로 가능한 모든 경로를 확인하는 접근 방식 보다 효율적
• 거리 뿐만 아니라 경로를 추적하도록 알고리즘을 쉽게 수정 가능

단점

• 우선순위 대기열을 사용할 때 간선이 많은 그래프의 경우 느려짐

다익스트라 알고리즘 사용 문제

백준 - 얼음 미로