다익스트라

어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점에서 각 노드들까지 최단 경로 문제를 푸는 알고리즘

위 그래프를 봅시다. 우리는 먼저 다익스트라 알고리즘을 풀기 위한 그래프의 조건을 알아야 합니다. 다익스트라는 위 그림처럼 음수 가중치를 갖지 않는 유향 그래프여야 합니다.

또한 출발점이 정해져있습니다. 위 그림에서는 파란색으로 칠해져 있는 0번 노드입니다. 이 출발점으로부터 각 노드까지의 최단경로를 모두 구할 수 있습니다.

다익스트라는 다음과 같이 작동합니다.

① 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 하나 선택해 방문한다. ② 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다.

맨 처음에는 시작점으로의 거리만 0이고 나머지는 다 거리가 무한(Inf)입니다. 정점 i, j 사이의 거리를 d[i][j], 거리 테이블을 dist라고 부르겠습니다.

추가로, 다익스트라는 우선순위 큐를 활용해 구현하는데요, 우선순위큐는 로직을 전부 이해한 후 맨 아래에서 설명하도록 하겠습니다. 일단은 배제하고 봐주세요!

우선순위큐 : (거리 0, 노드 1)

먼저 시작점에서 갈 수 있는 정점은 1과 7이 있습니다. 이 둘까지의 거리 정보를 통해, 노드 1까지의 최소거리는 1, 노드2까지의 최소거리는 7로 갱신됩니다.

그러면 dist 배열은 다음과 같이 갱신됩니다.

우선순위큐 : (거리 1, 노드 1), (거리 7, 노드 2)

그 다음, 아직 방문하지 않은 정점 중 dist가 제일 작은 곳이 1번이므로 1번 정점을 방문하여 인접한 3, 5번 정점의 거리 갱신을 시도합니다.

위와 같은 논리로 노드1에서 노드3까지의 거리는 9, 노드1에서 노드5까지의 거리는 15로 갱신됩니다. 따라서 노드0에서 노드 3까지의 거리는 10(dist[1]+d[1][3]), 노드 5까지의 거리는 16(dist[1]+d[1][5])으로 갱신되겠죠?

우선순위 큐 : (거리 7, 노드 2), (거리 10, 노드 3), (거리 16, 노드 5)

이제 위 dist에서 아직 방문하지 않은 정점 중 dist가 가장 작은 노드2에서부터 거리를 갱신합니다. 노드2를 거쳐 노드4로 가는 최소 거리는 7+4=11(dist[2]+d[2][4])입니다.

우선순위 큐 : (거리 10, 노드 3), (거리 16, 노드 5), (거리 11, 노드 4)

다음으로 아직 방문하지 않은 정점 중 dist가 가장 작은 노드3을 통해 가는 경로를 갱신합니다.

5번 노드는 dist[3]+d[3][5]가 dist[5]보다 작기 때문에 갱신됩니다. 여기서 노드4의 경우에는 거리가 갱신되지 않습니다. 이미 이전 경로가 더 가깝기 때문이죠. dist[4]가 dist[3]+d[3][4]보다 이미 작습니다.

우선순위 큐 : (거리 16, 노드 5), (거리 11, 노드 4), (거리 15, 노드5)

위와 같은 로직으로 노드4에서 노드5까지의 거리를 갱신하면 끝입니다!

우선순위 큐 : (거리 16, 노드 5), (거리 15, 노드5), (거리 14, 노드 5)

다익스트라 기본 문제 1753번을 풀어봅시다.

위에서 보면 아직 방문하지 않은 노드 중 dist가 가장 작은 노드부터 파악하는 로직을 눈치챌 수 있는데요, 우리는 이를 우선순위 큐로 구현할 수 있습니다.

먼저 최소 힙을 하나 마련합니다. 그리고 정점 u를 방문해서 인접한 정점 v의 거리를 갱신할 때마다 최소 힙에 (dist[v], v) 쌍을 넣습니다. 우선순위 큐는 배열 형태로 값이 들어온다고 하더라도 배열의 가장 첫번째 인자의 대소 비교를 먼저 하기 때문에 dist[v]값이 작은 아이부터 우선순위 큐에서 먼저 나오게 됩니다.

이제 다시 위에서 우선순위 큐의 모습을 살펴보세요. 굵은 글씨로 표현된 것이 최소힙의 heap[0]값이 되어 heappop을 하면 자동적으로 꺼내지는 가장 작은 dist값을 가진 노드에 해당합니다.

이 때 중요한 포인트는 연결된 3,5번 노드들과 시작 노드들 간의 거리가 이전보다 최단 거리로 업데이트될 경우에만 우선순위 큐에 집어넣습니다. 위 표에서 노드3을 통해 가는 경로를 갱신할 때 노드4에 해당하는 경로는 업데이트가 되지 않기 때문에 우선순위 큐에 들어가지 않는 것을 확인할 수 있죠?

그렇다면 우선순위 큐에 만약 노드N까지의 거리 정보가 두 개 이상 삽입된다면 어떻게 처리해야 할까요? 위 그래프에서는 마지막 상황에 해당합니다.

빨간색 글씨로 쓰인 노드 정보들을 봅시다. 이런 상황에서는 일단 가장 작은 값으로 노드가 한 번 처리된다면 다음 번에 처리될 나머지 노드들은continue로 무시해야 합니다.

아래 코드로 위 내용을 구현할 수 있습니다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

import heapq

# 정점의 개수 n, 간선의 개수 m
n, m = map(int, input().split())

# 시작 정점의 번호
k = int(input())

# 무한을 의미하는 INF
INF = int(1e9)

# 그래프 초기화
graph = [[] * (n+1) for _ in range(n+1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)

# 간선 정보 입력
for _ in range(m):
    a, b, c = map(int, input().split())
    # a->b가 c비용
    graph[a].append((b, c))


def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    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]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

# 다익스트라 알고리즘을 수행
dijkstra(k)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])

[참고] 아래는 위 상황을 모두 합친 동영상입니다.

풀어볼 문제

조금 난이도가 있으니 다익스트라 로직을 모두 이해하고 풀어보길 바랍니다.

PreviousDFSNext유니온 파인드(분리집합)

Last updated