다익스트라 코드

import heapq
from collections import defaultdict


def dijkstra1(start):
    # 힙 = (거리, 노드)
    # 시작 노드는 자신과의 거리 0
    h = [(0, start)]
    distance = defaultdict(lambda: INF)
    while h:
        cost, node = heapq.heappop(h)
        if node not in distance:
            # 해당 node 를 처음 방문한 순간이 최소 거리이다.
            distance[node] = cost
            for v, w in graph[node]:
                alt = cost + w
                if v not in distance:
                    heapq.heappush(h, (alt, v))
    print(sorted(distance.items()))

def dijkstra2(start, n):
    distance = [INF] * (n + 1)
    distance[start] = 0
    h = [(0, start)]
    while h:
        cost, node = heapq.heappop(h)
        if cost > distance[node]:
            continue
        for v, w in graph[node]:
            alt = cost + w
            if alt < distance[v]:
                distance[v] = alt
                heapq.heappush(h, (alt, v))
    print(distance[1:])

INF = float('inf')
nodes = [[1, 2, 2], [1, 3, 5], [1, 4, 1], [2, 3, 3],
         [2, 4, 2], [3, 2, 3], [3, 6, 5], [4, 3, 3],
         [4, 5, 1], [5, 3, 1], [5, 6, 2]]

graph = defaultdict(list)
for u, v, w in nodes:
    # 출발 노드 u, 도착 노드 v, 거리 = w
    graph[u].append((v, w))
n = 6
start = 1
dijkstra1(start)
print()
dijkstra2(start, n)

학습한 내용

1. 코드

dijkstra1 과 dijkstra2 둘 다 다익스트라 코드이다.

위의 코드를 더 선호하긴 하지만 합승 택시 요금 문제에서 dijkstra2 코드가 훨씬 빠른 시간복잡도를 가졌기 때문에 아래 코드 또한 기억하고 있어야겠다.

만약 dijkstra1 코드의 defaultdict 부분이 defaultdict(int) 였다면, 주변 노드들과 연결되지 않고 단절된 노드를 start 인자로 함수를 실행한다면 도착할 수 없는 주변 노드들의 거리가 기본값인 0으로 출력될 수 있으니 이 부분을 항상 조심해야 한다.

2. 다익스트라 알고리즘

다익스트라 알고리즘은 주변 노드 중 항상 최단 경로를 선택하여 최단 경로를 찾아내는 알고리즘이다. 다익스트라 알고리즘은 임의의 노드를 방문 집합에 처음 추가할 때, 그 노드까지의 최단거리는 그 순간 결정된다는 특징이 있다.

다익스트라 알고리즘은 주변 노드를 탐색할 때 BFS 알고리즘을 사용한다. 일반적인 BFS 에서는 연결된 모든 노드의 가중치(=거리, 비용)가 없기 때문에 큐에 들어온 순서대로 값을 꺼내기만 하면 된다. 하지만 다익스트라 알고리즘에서는 가중치가 존재하며 여러 가중치 중 최소값을 선택해야 한다.

이 최소 값을 찾는 과정에서 최소 힙을 사용한다면 노드의 개수(V), 간선의 개수(E) 일때, 인접 리스트 방식의 BFS와 힙의 시간복잡도를 곱한 O((V+E)logV) = O(ElogV)이 시간복잡도가 된다.

++
인접 행렬을 사용한 DFS, BFS = O(V^2)
인접 리스트를 사용한 DFS, BFS = O(V+E)