다익스트라(Dijkstra) 알고리즘

특정 정점까지 가는데 최소 비용을 찾는 알고리즘이다.

실생활에서 네비게이션에서 빠른길 찾기의 개념과 유사하다. 

 

시작점이 주어지고, 특정 정점까지 오는데 가중치를 최소비용으로 계산하면 된다. 

 

distances에 각 정점에 도착하는 최소비용을 저장, 나중에 특정 정점을 꺼내오면 된다.

distances는 구현하기 나름이긴한데, 정점이 영문이면 dictionary를 사용하고 숫자면 list를 쓰면 된다.

물론 둘다 dictionary를 사용하기도 한다. 

 

그리고 다익스트라는 힙을 사용해서 구현한다. (python에서는 heapq모듈을 사용하는데, 최소 비용으로 자동 정렬되기 때문이다. 

 

처음에 distances(각 정점에 도달하는 비용)은 무한대로 잡아놓고, 출발점만 0으로 잡는다. 

이렇게 하는 이유는 얼마가 최소 비용인지 모르기때문에 일단 최대치로 잡아 놓는 것이다. 

 

def dijkstra():
    graph = {
        'A' : [('B', 8), ('C', 1), ('D',2)],
        'B': [],
        'C': [('B', 5), ('D', 2)],
        'D':[('E', 3), ('F', 5)],
        'E': [('F', 1)],
        'F': [('A', 5)],
    }
    start = 'A'
    
    # 각 node에 도착하는 최소 비용을 저장하는 Dict
    distances = {node:float('inf') for node in graph}

    distances[start] = 0
    q = []
    # queue에 (비용, 정점)을 저장한다. 최소 heap이기 때문에 비용순으로 정렬이 된다.
    heapq.heappush(q, (distances[start], start))

    while q:
        # heap에서 하나 꺼내오고 
        current_distance, current_destination = heapq.heappop(q)
        # 기존 거리보다 길다면 탐색 안하는 버전, 꺼낸 값이 현재 값보다 작다면 궂이 탐색을 할 필요가 없다.
        if distances[current_destination] < current_distance:
            continue
        #현재 정점에서 연결된 곳을 모두 가져와 q에 집어 넣자
        for new_destination, new_distance in graph[current_destination]:
            # 현재 정점에 연결된 정점들을 돌면서 값을 갱신해주자
            # 비용이 작을때만 바꿔준다. 
            distance = current_distance + new_distance
            if distance < distances[new_destination]:
                distances[new_destination] = distance
                heapq.heappush(q, (distance, new_destination))

    #distances에 각 node에 오는 최소 비용이 담겨 있음
    print(distances)

 

leetcode의 743번을 풀어보자

leetcode.com/problems/network-delay-time/