분류

  • 최단 경로 알고리즘
  • 동적 계획법

알고리즘 코드 (반목문)

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
INF = int(1e9)  # 무한대

def dijkstra(A, n, start):
    '''
    A: 인접 행렬
    n: 정점의 개수
    start: 시작 정점
    '''
    D = A[start]  # 최단 거리
    V = [False] * n  # 방문 여부
    V[start] = True

    for i in range(n-1):  # 시작 노드를 제외하면 n-1개의 정점을 선택할 것임
        m = INF
        current = 0
        for j in range(len(D)):
            if not V[j] and D[j] < m: # 방문하지 않은 노드 중에 최소 정점 선택
                m = D[j]
                current = j
				
        V[current] = True
        for j in range(n):
            if not V[j] and D[current] + A[current][j] < D[j]:  # 기존 비용보다 저렴할 때 교체
                D[j] = D[current] + A[current][j]

    return D

알고리즘 코드 (최소 힙)

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
import heapq  # 최소 힙 사용

INF = int(1e9)  # 무한대

def dijkstra(A, n, start):
    '''
    A: 인접 리스트
    n: 정점의 개수
    start: 시작 정점
    '''
    D = [INF] * n  # 최단 거리
    D[start] = 0

    heap = [(0, start)]
    while heap:
        d1, cur = heapq.heappop(heap)  # 최소 정점 선택

        if D[cur] < d1:  # 최단 경로가 아닌 경우 스킵
            continue

        for d2, i in A[cur]:
            if d1 + d2 < D[i]:  # 기존 비용보다 저렴할 때 교체
                D[i] = d1 + d2
                heapq.heappush(heap, (D[i], i))

    return D

설명

최단 경로를 찾을 수 있는 대표적인 알고리즘 중 하나이다.

최소 정점을 찾아다니면서 기존 경로와 비교하는 동적 계획법 알고리즘이다.

최소 정점을 찾을 때 반목문을 이용한 구현과 최소 힙을 이용한 구현 두가지가 존재한다.

최소 힙을 사용하면 $V^2$의 복잡도에서 $ElogV$의 복잡도까지 줄일 수 있다.

복잡도

  • 반복문 $O(V^2)$
  • 최소 힙 $O(ElogV)$