최단 경로 문제

다익스트라 알고리즘

다익스트라 최단 경로 알고리즘은 그래프 이론에서 중요한 알고리즘 중 하나로, 특정 출발점에서 다른 모든 점으로 가는 최단 경로를 찾는 데 사용된다. 이 알고리즘은 단방향 그래프나 가중치가 있는 그래프에서 특히 유용하다. 다익스트라는 그리디 알고리즘에 속하며, 매 단계에서 ‘가장 비용이 적은 노드’를 선택하여 최단 경로를 확정한다.

방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다.
해당 노드를 거쳐 다른 노드를 가는 비용을 계산하여 최단거리 테이블을 갱신한다.
위 과정을 더 수행할 수 없을 때까지 반복한다.

‘각 노드에 대한 출발 노드에서부터 현재까지의 최단 거리’를 1차원 리스트에 저장해두고, 계속하여 갱신해나간다는 특징이 있다.

예시 코드 1 - 간단한 다익스트라

INF = int(1e9)

n, m = map(int, input().split())
start = int(input())

graph = [[] for i in range(n + 1)]
visited = [False] * (n + 1)
distance = [INF] * (n + 1)

# 단방향 그래프 입력 받기
for _ in range(m):
    a, b, cost = map(int, input().split())
    graph[a].append((b, cost))

# 방문하지 않은 노드 중 거리가 가장 짧은 노드의 인덱스 반환
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):
    # 1. 출발 노드와 연결된 노드의 최초 거리로 재설정
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]
    # 2. 최단 노드(get_smallest_node)를 불러와 거리 테이블 갱신
    for i in range(n-1):
        now = get_smallest_node()
        visited[now] = True
        for j in graph[now]:
            # 출발지에서 자신을 거쳐 가는 비용(cost) 계산
            cost = distance[now] + j[1]
            # 만약 cost가 더 효율적이라면 갱신
            if cost < distance[j[0]]:
                distance[j[0]] = cost

dijkstra(start)
print(* distance)

간단한 다익스트라 알고리즘은 직관적이며 구현에 적용하기 편리하지만, 시간 복잡도가 O(V^2)으로 다소 높다. 거리 테이블을 최종 갱신하기 위해 모든 노드를 조회하며, 각 노드마다 해당 노드를 거쳐 다른 노드에 도착하는 모든 경우를 일일이 확인하기 때문이다.

예시 코드 2 - 개선된 다익스트라

개선된 다익스트라 알고리즘은 최악의 경우에도 시간복잡도 O(ElogV)를 보장하여 더 효율적으로 작동한다. ‘간단한 다익스트라’ 알고리즘의 경우, 최단 거리가 가장 짧은 노드를 찾기 위해 getsmallestnode() 함수를 사용했다. 이 과정에서만 모든 노드를 조회하며 O(V) 시간이 소요되었다. 개선된 다익스트라에서는 힙 자료구조를 사용하여, 리스트가 항상 정렬되어 있음을 보장한다. 따라서, 힙에서 꺼내는 원소 = 최단 노드가 된다.

from heapq import heappop, heappush
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())

graph = [[] for i in range(n + 1)]
distance = [INF] * (n + 1)

# 단방향 그래프 입력 받기
for _ in range(m):
    a, b, cost = map(int, input().split())
    graph[a].append((b, cost))

# 개선된 다익스트라 알고리즘
def dijkstra(start):
    # 1. 우선순위 큐를 선언 후, 출발 노드 삽입
    q = []
    heappush(q, (0, start))
    distance[start] = 0
    # 2. 최단 노드를 꺼내 거리 테이블 갱신
    while q:
        path, node = heappop(q)
        # 이미 최단 거리가 더 짧은 경우 생략
        if distance[node] < path:
            continue
        # 출발지에서 자신을 거쳐 가는 비용(new_cost) 계산
        for b, cost in graph[node]:
            new_cost = path + cost
            # 만약 new_cost가 더 효율적이라면 갱신, 큐에 삽입
            if new_cost < distance[b]:
                distance[b] = new_cost
                heappush(q, (new_cost, b))

dijkstra(start)
print(* distance)

개선된 다익스트라는 E개의 원소를 우선 순위 큐에 넣었다가 모두 빼내는 연산을 포함한다. 힙 자료구조에 N개의 원소를 모두 넣고 빼는 과정은 O(N log N)의 시간복잡도를 가지므로, O(E log E) 의 시간복잡도를 가짐을 이해할 수 있다. 이 때, E는 항상 V^2보다 작거나 같으므로 O(E log V)로 표현할 수 있다.

플로이드 워셜 알고리즘

다익스트라 알고리즘은 특정한 출발 노드에서 시작해 다른 노드까지의 최단 경로를 구하는 알고리즘이다. 반면, 플로이드 워셜은 ‘모든 노드에서 다른 모든 노드로의 최단 경로를 구하는’ 알고리즘이다. 따라서, 1차원 거리 테이블(distance)에 모든 최단 거리를 저장하는 다익스트라와 달리 2차원 테이블에 최단 거리 정보를 저장한다는 특징이 있다. 시간복잡도는 O(N^3)이다.

INF = int(1e9)

n = int(input())
m = int(input())

graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신으로의 거리는 0으로 설정
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 그래프 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = c

# 현재 저장된 최단 거리와 비교하며 갱신
for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

print(* graph)

최단 경로 문제

SERIES: 알고리즘 (9)

다익스트라 알고리즘

예시 코드 1 - 간단한 다익스트라

예시 코드 2 - 개선된 다익스트라

플로이드 워셜 알고리즘

추천 문제