다익스트라 알고리즘[Python]

정의

다익스트라 알고리즘은 방향그래프에서 단일 출발점에서의 각 정점으로의 최단 경로를 구하는 알고리즘입니다.

알고리즘 문제에서 다익스트라 알고리즘은 가중치 그래프에서의 최단 경로를 탐색하는 문제입니다.

 

과정

1. 시작 노드에서 각 노드의 최소 비용을 저장한다.

2. 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택한다.

3. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.

4. 위 과정을 반복한다.

 

위 과정을 진행하기 위해선 인접행렬 그래프를 사용합니다.

https://velog.io/@diddnjs02/%EC%A0%9C%EB%8C%80%EB%A1%9C%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC

 

위와 같은 그래프가 있다고 가정할 때, 인접행렬로 그래프를 구성하면 아래와 같습니다.

0	2	3	INF	INF
INF	0	4	5	INF
INF	INF	0	6	INF
INF	INF	INF	0	INF
1	INF	INF	INF	0

INF는 갈 수 있는 경우가 아닐 때 최소 거리를 무한으로 설정하면서 표시하였습니다.

 

이제부터 파이썬으로 위 그래프의 다익스트라 알고리즘을 구현해보도록 하겠습니다.

그러나 위 그래프를 직관적으로 구현하면, 간선의 수가 비정상적으로 적은경우 시간복잡도가 굉장히 많이 발생합니다.

이를 해결하기 위해서 우선순위 큐를 사용합니다. 우선순위 큐를 사용하면 노드에서 찾을 수 있는 가장 짧은 간선을 찾는데 시간이 크게 단축됩니다

O(|V|^2+|E|) ->  O(|E|log|E|)

 

구현

위 그래프를 우선 코드로 표현해주어야 합니다. 코드로 표현하는건 처음이다보니 아래 블로그를 참고하였습니다.

https://greenhelix.tistory.com/130

Dijkstra Algorithm :: 다익스트라 알고리즘 (최단경로)

 

1. 딕셔너리로 그래프간 가중치와 연결정보를 표현

MAP = {
    'A' : {'B': 2, 'C' : 3},
    'B' : {'C' : 4, 'D' : 5},
    'C' : {'D' : 6},
    'D' : {},
    'E' : {'A' : 1}
}

 

2. 우선순위 큐를 이용하여, 가장 비용이 적은 간선을 pop한다.

3. 이전의 이동 비용과, 새로 계산한 거리를 비교하여 더 작은 비용을 가진 노드를 선택한다.

4. 과정을 반복한다.

    while heap:
        # print("heap",heap)
        current_distance, now_position = heapq.heappop(heap)    # 0, 'A'
        print(country[now_position], current_distance)
        if country[now_position] < current_distance:    # 현재 position이 이전 position보다 작으면
            continue                                    # 넘어간다

        # print("road_item :", road[now_position].items())

        for arrival, weight in road[now_position].items():
            distance = current_distance + weight
            if distance < country[arrival]: #도착지 거리가 현재 계산한 거리보다 작으면
                country[arrival] = distance #둘이 바꾼다
                heapq.heappush(heap, [distance, arrival])   #힙에 추가

        #     print("dist :",country[arrival])
        # print("\n\n\n")
    return country