Dijkstra.md

최단 경로 알고리즘

• 가장 짧은 경로를 찾는 알고리즘 (길 찾기)

• 주로 그래프를 통해 표현

• 각 지점은 '노드', 지점간 연결된 도로는 '간선'으로 표현

• 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘

다익스트라 최단 경로 알고리즘

• 특정 노드에서 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘

• '음의 간선'이 없을 때 정상적으로 작동

  • 음의 간선: 0보다 작은 값을 가지는 간선

'가장 비용이 적은 노드'를 선택하는 임의의 과정 반복이므로 그리디 알고리즘으로 분류

알고리즘의 원리

1. 출발 노드를 선택

2. 최단 거리 테이블로 초기화

3. 방문하지 않은 노드 중, 가장 짧은 최단 거리 노드를 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산 후 최단 거리 갱신

5. 3과 4 과정을 반복

'현재까지 각 노드에 대한 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 갱신

1. 간단한 다익스트라 알고리즘

• O(V^2)의 시간 복잡도 (V: 노드의 개수)

• 특정 노드를 출발으로 하는 1차원 리스트를 생성

• 각 단계마다 '방문하지 않은 노드 중 최단거리가 짧은 노드를 선택' -> 1차원 리스트 모든 원소 탐색

그래프를 표현할 때는 리스트의 크기를 (노드의 개수 + 1)로 할당하자.

노드의 번호를 인덱스로 하여 리스트에 바로 접근하기 좋다.

• 전체 노드의 개수가 5000개 이하면 일반적으로 해당 방법을 사용 가능

• 노드의 개수가 10000개를 넘어가면 개선된 다익스트라 알고리즘을 사용해야 함

2. 개선된 다익스트라 알고리즘

• O(ElogV)의 시간 복잡도 (V: 노드의 개수, E: 간선의 개수)

• 힙 자료구조를 사용하여 최단 거리의 노드를 더욱 빠르게 찾을 수 있음

  • 이전 1차원 리스트 인덱스를 모두 도는 선형 시간이 아닌 로그 시간이 걸림

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙	O(logN)	O(logN)

PriorityQueue보다 통상적으로 heapq가 빠르다.

• 이후 최단거리를 갱신하는 방법은 1번 방법과 동일하다.

추가로 2차원 배열을 통해 간선과 시간을 계산하는 방법보다 인접 리스트를 통하면 더 빠르게 계산 가능

---

다익스트라 예제

파티_1238

import sys
import heapq
input = sys.stdin.readline

N, M, X = map(int,input().split())

graph = [[] for _ in range(N+1)]
for _ in range(M):
    a,b,c = map(int, input().split())
    # 인접 리스트를 통해서 정보 처리
    graph[a].append((b,c))

def dijkstra(start, g):
    # 시작점에서 모든 경로 초기화
    dist = [float('inf')] * (N+1)
    dist[start] = 0
    q = [(0, start)]

    while q:
        now_t, now = heapq.heappop(q)
        if now_t > dist[now]:
            continue
        for next, weight in g[now]:
            total_t = now_t + weight
            if total_t < dist[next]:
                dist[next] = total_t
                heapq.heappush(q, (total_t, next))

    return dist

# X에서 모든 정점으로의 최단 경로
all_from_X = dijkstra(X, graph)

# 모든 정점에서 X로의 최단 경로
all_to_X = [0] * (N+1)
for i in range(1, N+1):
    if i != X:
        all_to_X[i] = dijkstra(i, graph)[X]

max_t = max(all_from_X[i] + all_to_X[i] for i in range(1, N+1) if i != X)
print(max_t)

모든 노드에서 특정 노드 X로 향하는 최단시간과

특정 노드 X에서 모든 노드로 향하는 최단시간 두 가지 경우를 계산해야한다.

해당 문제에서 동일한 다익스트라 메서드 dijkstra(start, g) 을 사용해 두 가지 경우를 계산했다.

2차원 배열 대신 인접 리스트를 통해서 처리하게되면 희소 그래프(간선의 값이 없는 경우가 많은 그래프)에 대해서 더 효율적으로 값을 처리 가능하다.