Post

데이크스트라 알고리즘

Posted
By Park "ShapeLayer" Jonghyeon
12 min read
데이크스트라 알고리즘

도입

그래프 문제에서 BFS와 DFS는 용이하게 사용된다. 하지만 BFS/DFS는 간단한 형태의 그래프에서만 제대로 사용할 수 있다.

BFS/DFS에서는 모든 간선을 동일한 것으로 가정했다. BFS/DFS에서의 정점 간의 거리는, 시작 정점으로부터 도착 정점까지 이동하는 과정에서 정점을 방문한 횟수로 계산되었다. 모든 간선의 거리를 1로 간주한 것이다.

만약 각 간선에 가중치가 부여되어 모든 간선의 거리를 동일시할 수 없다면, BFS/DFS를 그대로 사용하기 어렵다. 알고리즘을 확장하여야 한다.


NOTE: 아래에서 “가중치”와 “거리”, “비용”을 혼용해서 사용하고 있다. 이들은 같은 의미로 사용하고 있다.

BFS로부터 확장하기

정지 조건 수정

BFS의 구현에서 핵심은 큐를 사용하여 다음 반복 과정에서의 탐색을 예약하고, 다음 반복 과정에서 큐에서 예약한 작업을 인출하여 처리하는 것이었다.

이 과정에서 한 번 처리한 내용을 다시 반복해 처리하지 않도록 소위 visited 배열, 방문 처리를 기록하는 데이터를 따로 두었다. 정점의 방문 여부가 반복을 계속 진행할지, 즉 정지 조건을 결정하는 기준이 되었다.


방문 여부를 정지 조건으로 사용하는 대신 현재까지 파악한 시작점과의 거리보다 지금 계산한 거리가 더 짧은지 여부를 정지 조건으로 사용하는 것으로 가중치가 있는 간선에 대해서도 최단 거리를 구할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

dist_from_start: list[int]
q: deque[int] = deque()

while q:
  now = q.popleft()

  # conn: list[list[tuple[int, int]]]
  # conn[now]: list[tuple[int, int]] = [(점A로의 가중치, 점A), (점B로의 가중치, 점B), ...]
  for next_cost, next_node in conn[now]:
    # (이전) BFS:
    # if visited[next_node]:
    #   continue

    # (수정) 데이크스트라:
    if dist_from_start[next_node] <= dist_from_start[now] + next_cost:
      continue

    dist_from_start[next_node] = dist_from_start[now] + next_cost
    q.append((next_cost, next_node))

수정된 정지 조건은 이미 방문한 정점이더라도, 상황에 따라서 계속해서 방문할 수 있다. 지금까지 파악한 시작점으로부터의 거리가 최단 거리가 아님이 확인되면 다시 방문하여 거리를 갱신하고, 주변 노드에 대해서도 자신의 갱신 처리에 대응하도록 처리 큐에 예약한다.

이러한 반복 과정이 충분히 수행된다면 dist_from_start[next_node] <= dist_from_start[now] + next_cost는 모든 정점에서 참이 된다.


정지 조건이 초기에 잘 수행되려면 dist_from_start는 매우 큰 값INF으로 채워져야 한다. 만약 0 혹은 음수로 채워져있다면, 정지 조건에 의해 반복 과정이 continue되지 않도록 추가적으로 분기 처리를 해야한다.

큐 구현체 변경

정지 조건을 현재까지 파악한 시작점과의 거리보다 지금 계산한 거리가 더 짧은지 여부로 변경하면서 발생하는 또 다른 문제는, 큐에 지나치게 많은 정점이 예약될 수 있다는 것이다.

큐는 항상 먼저 삽입된 값을 먼저 인출하므로, 최악의 경우에는 가능한 모든 경로가 조합되어 각 정점과 시작점과의 거리가 매우 순차적으로 감소할 수 있다.


비교 상황으로 큐를 우선순위 큐로 대체할 수 있다. 우선순위 큐에 다음에 처리할 정점과 함께 해당 정점으로 가는 경로의 비용을 삽입한다. 이어서 낮은 값만을 꺼내도록 하면 매 반복 순간, 가장 비용이 낮은 경로를 우선적으로 처리할 수 있다.

예약된 처리들 중 가장 비용이 낮은 처리를 수행하였으므로, 큐에 남아있는 다른 예약 처리들은 정지 조건, 현재까지 파악한 시작점과의 거리보다 지금 계산한 거리가 더 짧은지 여부(dist_from_start[next_node] <= dist_from_start[now] + next_cost)에 의해 더 이상 작업을 예약하지 않는다.1

1 정확히는 같은 간선을 지나는 다른 경로에 대한 처리

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

from heapq import heappop, heappush
dist_from_start: list[int]
q: list[tuple[int, int]] = []

while q:
  cost, now = heappop(q)

  # conn: list[list[tuple[int, int]]]
  # conn[now]: list[tuple[int, int]] = [(점A로의 가중치, 점A), (점B로의 가중치, 점B), ...]
  for next_cost, next_node in conn[now]:
    # (이전) BFS:
    # if visited[next_node]:
    #   continue

    # (수정) 데이크스트라:
    if dist_from_start[next_node] <= dist_from_start[now] + next_cost:
      continue

    dist_from_start[next_node] = dist_from_start[now] + next_cost
    heappush(q, (dist_from_start[next_node], next_node))

데이크스트라 알고리즘

BFS로부터 확장한 위의 알고리즘을 데이크스트라 알고리즘(Dijkstra’s algorithm)이라고 한다. 에츠허르 데이크스트라(Edsger Wybe Dijkstra)에 의해 제안되어 이와 같은 이름이 붙었다.

정리하여 데이크스트라 알고리즘을 구현하는 데에는 다음의 내용이 주요하게 구현되어야 한다.

  • 시작점으로부터의 거리(=시작점으로부터의 가중치 합산)을 기록하는 자료구조를 선언한다.
    • 이 자료구조는 매우 큰 값으로 초기화되어야 한다.
  • 우선순위 큐를 사용해 다음 탐색 작업을 예약하고, 가장 비용이 낮은 작업을 먼저 처리한다.
  • 탐색이 수행되는 각 반복 과정에서, 현재까지 파악한 시작점으로부터의 거리보다, 새로 계산한 거리가 더 짧은 경우에 값을 갱신하고 다음 처리를 예약한다.
    • 새로 계산된 거리 합계를, 이를 기록하는 자료구조에 저장한다.
    • 갱신된 정점과 정점에 대한 정보를 우선순위 큐에 삽입하고, 이후 반복 과정에서 같은 처리를 수행한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

INF = int(1e9)

def compute(V: int, E: int, K: int, conns: list) -> list[int]:
  """
  V: int = 정점의 개수
  E: int = 간선의 개수
  K: int = 시작 정점

  conns: list[list[tuple[int, int]]]
  conns[N]: list[tuple[int, int]] = [(점N→점A의 가중치, 점A), (점N→점B의 가중치, 점B), ...]
  """

  q = []
  # 1
  heappush(q, (0, K))
  costs = [INF] * (V + 1)
  costs[K] = 0

  while q:
    # 2
    cost, now = heappop(q)

    if costs[now] < cost:
      continue

    # 3
    for next_cost, _next in conns[now]:
      if costs[_next] >= costs[now] + next_cost:
        costs[_next] = costs[now] + next_cost
        heappush(q, (costs[_next], _next))

  return costs

백준 온라인 저지, 1753번: 최단 경로 문제 풀이, 주 처리 함수

BFS의 초기화 과정과 비슷하게, #1에서 최초 탐색 작업을 예약한다. q에는 (0, K) 튜플, (시작점으로부터 거리 합계 0, 시작점 K)를 삽입한다. 이어서 비용 합계 자료구조 costs를 선언하여 매우 큰 정수값1e10으로 초기화한다. 시작점 K는 시작점으로부터 거리 합계가 0이므로 costs[K] = 0으로 초기화한다.

#2에서 큐 q는 우선순위 큐이므로 비용이 가장 낮은 작업을 인출한다. 만약 costs[now] < cost라면, 이미 더 낮은 비용으로 해당 정점에 도달한 적이 있으므로, 지금 인출한 작업은 무시하고 다음 작업을 인출한다.

#3에서 현재 정점 now와 연결된 모든 정점에 대해서, 새로운 경로를 통해 더 짧은 거리를 발견한 경우에만 값을 갱신한다. 만약 값을 갱신했다면 다음 처리를 예약한다.

최종적으로 이 함수는 INF 혹은 시작점으로부터 최단거리 합계를 반환한다. 초기화 값 INF가 유지되는 시나리오는 시작점으로부터 시작한 탐색 처리가 해당 정점까지 도달하지 못하는 상황이다.

algorithm
ps baekjoon algorithm