Dijkstra Algorithm

어느 한 지점에서 모든 점으로 가는 최단 경로를 알고싶을때! 사용하는 다익스트라 알고리즘에 대해 알아보자

1. Dynamic Programming

놀랍게도 3주차 그래프 탐색을 공부하며 배웠던 다익스트라가 4주차에 배우는 DP를 사용하는 것이었다! (아무렇지도 않게 흡수했다니 나 혹시 dp 천재일지도?)

각설하고, 다익스트라는 그래프의 한 점으로부터 다른 모든 점까지의 '최단 거리의 경로'를 찾아주는 알고리즘이다. 이 과정에서 최솟값을 계속해서 갱신해나가는데, DP table 을 사용해 이미 계산된 결과는 바로 참조한다.

그런데, DP의 정의를 만족하는건가? 라는 생각이 들 수 있다.

최단거리는 여러 개의 최단거리로 이루어져 있기 때문에 DP 입니다. -동빈좌-

그렇다고한다.

2. Heapq

아래에서 코드를 통해 보이겠지만 다익스트라를 구현하는 과정에서 시간복잡도를 줄여주기 위해 힙구조를 사용한다. 일반 선형탐색으로 그래프를 탐색해 나간다면 굳이 비교를 안해도 되는 상황도 비교를 하게된다.

ex) 1번 노드에서 2번 노드를 거쳐 3번노드를 가는 최소 경로가 있다고 했을때, 1번에서 3번으로 바로 가는 경로 가중치가 최소값보다 크다면 테이블에서 불러올것도 없이 해당 경로는 보지않는다.
'꼭 똥인지 된장인지 찍어먹어봐야 아냐'와 같은 맥락이 아닐까

3. Code

아래 코드는 justkode 님의 블로그를 참조하였습니다. justkode

자세한 설명은 주석으로 대체 하겠다. :)

import heapq

def dijkstra(graph, start):
    # start 로 부터의 거리값을 저장하기 위함. 가장 큰값으로 되어있기 때문에
    # 최솟값으로 지속적으로 갱신될것.
    dist_list = {node: float('inf') for node in graph} 
    # 자기자신까지의 거리는 0 
    dist_list[start] = 0
    queue = []
    # start 지점을 heap queue 에서 꺼내서 시작. 
    heapq.heappush(queue, [dist_list[start], start])
    
    while queue:
        # 큐에서 탐색할 노드와 거리를 꺼내온다.
        # 파이썬 자료구조상 최소힙으로 설정되어있기때문에 우선순위는 거리가 짧은 순서대로 들어가 있을것. 
        current_distance, current_destination = heapq.heappop(queue)
        # 꺼낸 노드까지의 거리가 현재 distances 에 저장되어있는 거리보다 길다면 
        if dist_list[current_destination] < current_distance:
            # 볼 필요도 없이 넘어감. 
            continue
        # 위조건문을 넘어왔다면 graph 딕셔너리의 current_destination 에 해당하는 index 에서 key 값과 value 를 다 꺼내준다. 
        for new_destination, new_distance in graph[current_destination].items(): 
            # 거리는 new_distance를 더해서 갱신. distance 라는 새로운 변수 선언 
            dist_var = current_distance + new_distance
            if dist_var < dist_list[new_destination]:
                dist_list[new_destination] = dist_var
                # 현재 노드의 다음 노드로의 인접거리를 계산하기위해 큐에 삽입. 
                heapq.heappush(queue, [dist_var, new_destination])
    
    return dist_list

if __name__ == "__main__":
    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}
    }

    print(dijkstra(graph, 'A'))