[코딩 테스트 합격자 되기 - 8주차] 그래프(Graph) - 2

그래프 최단 경로 구하기

최단 경로는 그래프 종류에 따라 그 진의가 다르게 해석될 수 있는 주제. 최단 경로를 구하는 대표적인 알고리즘인 다익스트라 알고리즘과 벨만-포드 알고리즘을 알아보자.

 

다익스트라 알고리즘

다익스트라 알고리즘은 최단 경로를 구하는 알고리즘이면서 탐욕법(Greedy Algorithm)으로 분류되는 알고리즘이기도 하다.

1. 시작 노드를 설정하고 시작 노드로부터 특정 노드까지의 최소 비용을 저장할 공간과 직전 노드를 저장할 공간을 마련.
   1. 최소 비용을 저장할 공간은 매우 큰 값으로 초기화. (float('inf')) 직전 노드를 저장할 공간도 INF로 초기화함.
   2. 시작 노드의 최소 비용은 0, 직전 노드는 자신으로 한다.
2. 해당 노드를 통해 방문할 수 있는 노드 중 현재까지 구한 최소 비용이 가장 적은 노드를 선택.
   1. 해당 노드를 거쳐서 각 노드까지 가는 최소 비용과 현재까지 구한 최소비용을 비교하여 작은 값을 각 노드의 최소 비용으로 갱신.
   2. 이때 직전 노드도 같이 갱신
3. 노드 개수에서 1을 뺀 만큼 반복

이 일련의 과정을 그림과 함께 더 자세히 알아보자.

 

1. 시작 노드 A의 최소 비용은 0, 직전 노드는 A로 초기화.
2. 방문하지 않은 노드 중 최소 비용이 가장 적은 노드 A를 선택. 이후 해당 노드를 거쳐 각 노드까지 가는 비용과 기존에 구한 각 노드의 최소 비용을 비교한다. 노드 A에서 노드 B, C, E의 가중치는 각각 4, 4, 1. 현재 해당 노드의 최소 비용은 모두 INF이므로 각 B, C, E 의 최소비용을 더 적은 값인 4, 4, 1로 갱신. 이때 최소 비용이 갱신된 노드의 직전 노드도 A로 갱신.
3. 방문하지 않은 노드 중 최소 비용이 가장 적은 노드인 E를 선택. 선택한 노드를 거쳤을 때 최소 비용을 갱신할 수 있는지 확인. 노드 C의 현재 최소 비용은 4이며, E를 거쳤을 때의 최소 비용은 1과 E -> C 의 가중치 2를 합한 3이 된다. 이는 현재 C의 최소 비용인 4보다 더 적은 비용이기 때문에 3으로 갱신하고, 직전 노드도 E로 갱신한다.
4. 아직 방문하지 않은 노드 중 최소 비용이 가장 적은 노드 C를 선택. 선택한 노드를 거쳤을 때 최소 비용을 갱신할 수 있는지 확인. 노드 D의 경우, 기존 최소 비용이 INF이지만, C(3) -> D(8) 을 합쳐 11이 되어 INF => 11로 갱신하고, 직전 노드를 C로 갱신한다.
5. 방문 하지 않은 노드 중 최소 비용이 가장 적은 노드 B를 선택. 최소 비용이 발생할 수 있는지 확인하였지만, B -> C 가중치가 C의 최소비용보다 높아 방문만 하고 값을 갱신하지는 않는다.
6. 방문 하지 않은 노드 중 최소 비용이 가장 적은 노드 D를 선택. 역시 마찬가지로 방문만 하고 값을 갱신하지는 않는다.
7. 모든 곳을 방문하였으며, 각 노드의 최소 비용과 직전 노드를 갱신하였다. 시작 노드를 A로 하였을 때, 노드 C의 경우 최소 비용이 3이며, 직전 노드 E, 세부 경로는 A -> E -> C가 된다는 것을 확인할 수 있었다.

다익스트라 알고리즘을 코드로 표현하였다. 

def solution2(graph, start) :
    distances = {node: float("inf") for node in graph}  # ❶ 모든 노드의 거리 값을 무한대로 초기화
    distances[start] = 0    # ❷ 시작 노드의 거리 값은 0으로 초기화
    queue = []
    heapq.heappush(queue, [distances[start], start])    # ❸ 시작 노드를 큐에 삽입
    paths = {start : [start]}   # ❹ 시작 노드의 경로를 초기화

    while queue :
        # ❺ 현재 가장 거리 값이 작은 노드를 가져옴
        current_distance, current_node = heapq.heappop(queue)
        # ❻ 만약 현재 노드의 거리 값이 큐에서 가져온 거리 값보다 크면, 해당 노드는 이미 처리한 것이므로 무시
        if distances[current_node] < current_distance :
            continue

        # ❼ 현재 노드와 인접한 노드들의 거리 값을 계산하여 업데이트
        for adjacent_node, weight in graph[current_node].items() :
            distance = current_distance + weight
            # ❽ 현재 계산한 거리 값이 기존 거리 값보다 작으면 최소 비용 및 최단 경로 업데이트
            if distance < distances[adjacent_node] :
                distances[adjacent_node] = distance # 최소 비용 업데이트
                paths[adjacent_node] = paths[current_node] + [adjacent_node]    # 최단 경로 업데이트

                # ➒ 최소 경로가 갱신된 노드를 비용과 함께 큐에 푸시
                heapq.heappush(queue, [distance, adjacent_node])

    # ➓ paths 딕셔너리를 노드 번호에 따라 오름차순 정렬하여 반환
    sorted_paths = {node : paths[node] for node in sorted(paths)}

    return [distances, sorted_paths]