알고리즘

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

위시리 2025. 4. 3. 14:24

개념

다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(shortest Path) 탐색 알고리즘이다.

정점과 간선에 대하여 최단 경로를 구하는데, 이때 음의 간선은 포함할 수 없다.

다익스트라 알고리즘을 dp로 구현할 수 있는 이유는 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다.
즉, 작은 문제가 큰 문제의 부분 집합에 속해있다고 볼 수 있다.

기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다.

 

다익스트라 작동 방법

  1. 출발 노드를 설정한다.
  2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.
  3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
  4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.
  5. 위 과정에서 3~4번을 반복한다.
    1. 현재 노드에 대해 최단 비용 저장
    2. 방문하지 않은 노드 중 가장 적은 노드 선택 (heapq가 알아서 해줌)

 

example : https://m.blog.naver.com/ndb796/221234424646

https://m.blog.naver.com/ndb796/221234424646

위와 같은 그래프가 준비되어 있다고 할 때, 이러한 그래프는 실제로 컴퓨터 안에서 처리할 때 이차원 배열 형태로 처리해야 한다.

따라서 다음과 같이 특정 행에서 열로 가는 비용을 아래 표와 같이 나타낼 수 있다.

예를 들어 1행 3열의 값은 5라는 것을 알 수 있다.

1번 노드에 대해서, 1번 노드와 연결된 간선은 3개이고

1번 노드에서 다른 정점으로 가는 최소 비용은 다음과 같다. 배열을 만든 뒤, 이 최소 비용 배열을 계속 갱신할 것이다.

현재 방문하지 않은 노드 중 가장 비용이 적은 노드는 4번 노드이다.

따라서 위 배열의 상태를 고려하여 4번 노드가 선택(방문 노드)되었다. 4번 노드를 거쳐서 가는 경우를 모두 고려하여 최소 비용 배열을 갱신하면 된다.

 

(현재 노드 : 4)

기존 1 → 5로 가는 최소 비용은 무한이였다. 하지만 4를 거쳐서 5로 가는 경우는 비용이 2 이므로 최소 비용 배열을 갱신한다.

또한 4를 거쳐서 3으로 가는 경우는 비용이 4이므로 기존보더 저 저렴하다. 따라서 최소 비용 배열을 갱신해준다.

 

다음으로 방문하지 않은 노드 중에서 가장 비용이 적은 노드는 2번이다.

(현재 노드 : 2)

2를 거쳐 가더라도 비용이 갱신되는 경우가 없다. 따라서 배열은 그대로 유지된다.

...

 

구현

1. for

n, m = map(int, input().split())
k = int(input())                 # 시작할 노드
INF = 1e8

graph = [[] for _ in range(n+1)] # 1번 노드부터 시작하므로 하나더 추가

visited = [False] * (n+1)
distance = [INF] * (n+1)

for _ in range(m):
  u, v, w = map(int, input().split()) # u: 출발노드, v: 도착노드, w: 연결된 간선의 가중치 
  graph[u].append((v, w))             # 거리 정보와 도착노드를 같이 입력합니다.

def get_smallest_node():
  min_val = INF
  index = 0
  for i in range(1, n+1):
    if distance[i] < min_val and not visited[i]: 
      min_val = distance[i]
      index = i
  return index

def dijkstra(start):
  distance[start] = 0 # 시작 노드는 0으로 초기화
  visited[start] = True

  for i in graph[start]:
    distance[i[0]] = i[1] # 시작 노드와 연결된 노도들의 거리 입력
  
  for _ in range(n-1): 
    now = get_smallest_node() # 거리가 구해진 노드 중 가장 짧은 거리인 것을 선택
    visited[now] = True       # 방문 처리

    for j in graph[now]:
      if distance[now] + j[1] < distance[j[0]]: # 기존에 입력된 값보다 더 작은 거리가 나온다면,
        distance[j[0]]= distance[now] + j[1]    # 값을 갱신한다.

dijkstra(k)
print(distance)

 

2. heap

다익스트리는 힙구조를 통해 빠르게 연산할 수 있다.

n, m = map(int, input().split())
k = int(input())                 # 시작할 노드
INF = 1e8

graph = [[] for _ in range(n+1)] # 1번 노드부터 시작하므로 하나더 추가

distance = [INF] * (n+1)

for _ in range(m):
  u, v, w = map(int, input().split()) # u: 출발노드, v: 도착노드, w: 연결된 간선의 가중치 
  graph[u].append((v, w))             # 거리 정보와 도착노드를 같이 입력합니다.


import heapq

def dijkstra(start):
  q = []
  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]:     # 연결된 모든 노드 탐색
      if dist+i[1] < distance[i[0]]: # 기존에 입력되어있는 값보다 크다면
        distance[i[0]] = dist+i[1]   #
        heapq.heappush(q, (dist+i[1], i[0]))
dijkstra(k)
print(distance)

 

연습문제

백준 1753 최단경로

https://wishlee0204.tistory.com/217

 

 

 

저작자표시