김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

다익스트라 알고리즘

개요

다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다.
즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다.
단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-포드 알고리즘을 사용해야 한다.

기본적인 아이디어는 다음과 같다:
\(\delta(u, v)\)를 \(u\)에서 \(v\)로의 최단거리라고 할 때, \(\delta (u, v)\)의 부분경로는 마찬가지로 최단거리를 가지는 경로가 된다.
다시 말해, 최단경로의 부분경로는 마찬가지로 최단경로이다.

다익스트라 알고리즘의 대략적인 순서는 이렇다:

  1. 출발점에서 각 노드까지의 거리를 무한대로 초기화한다.
  2. 출발점에서 출발점까지의 거리는 0으로 초기화한다.
  3. 모든 노드에 대해 다음의 과정을 반복한다.
    1. 방문하지 않은 노드 중 현재 거리가 가장 가까운 노드를 선택한다.
    2. 선택한 노드의 인접 노드에 대해 다음 과정을 반복한다.
      1. (출발점과 각 노드의 거리) = min((출발점과 선택한 노드의 거리) + (선택한 노드와 각 노드의 거리), (출발점과 각 노드의 거리))

예시

image
위 그래프에서 출발점이 A노드라고 하자.

image
초기화 이후 거리는 위와 같을 것이다.

image
처음에 가장 거리(0)가 가까운 노드 A가 선택되고, 그 인접 노드(B, C)까지의 거리가 갱신된다.

image
이후 그 다음으로 거리(2)가 가까운 노드 C가 선택되고, 그 인접 노드(B)까지의 거리가 갱신된다.
그 후에는 B(거리: 3)가 선택되지만, 갱신되는 노드는 없다.
결과적으로 출발점 A에서 각 노드까지의 거리는 0, 3, 2, INF(경로 없음)가 된다.

구현

다익스트라 알고리즘은 우선순위 큐를 활용하면 효율적으로 구현할 수 있다.
가장 가까운 노드를 선택할 때, 선형 탐색(\(O(N)\))을 하는 것보다 최소 힙을 이용한 우선순위 큐(\(O(lgN)\))를 활용하는 것이 더 효율적이기 때문이다.
또한, 우선순위 큐를 사용하면 도달한 노드가 큐에서 빠지므로 방문 처리를 위한 배열이 필요하지 않게 된다.

from heapq import *
INF = float('inf')

# 연결 리스트로 구현된 그래프
graph = [[(1, 4), (2, 2)], [], [(1, 1)], [(0, 1)]]
n = len(graph)

# 거리를 나타내는 리스트, INF로 초기화
distance = [INF] * n
distance[0] = 0

# 최소 힙 우선순위 큐
q = []
heappush(q, (0, 0))

# 다익스트라 알고리즘 진행
while q:
    cost, node = heappop(q)
    if distance[node] < cost:
        continue
    for nextNode, nextCost in graph[node]:
        if distance[node] + nextCost < distance[nextNode]:
            distance[nextNode] = distance[node] + nextCost
            heappush(q, (distance[nextNode], nextNode))

# 각 노드까지의 거리 출력
print(distance)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑