[패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 31회차 미션

4. 다익스트라 알고리즘 파이썬 구현 (우선순위 큐 활용까지 포함)

참고: heapq 라이브러리 활용을 통해 우선순위 큐 사용하기

- 데이터가 리스트 형태일 경우, 0번 인덱스를 우선순위로 인지, 우선순위가 낮은 순서대로 pop 할 수 있음

 

import heapq

 

queue = []

 

heapq.heappush(queue, [2, 'A'])

heapq.heappush(queue, [5, 'B'])

heapq.heappush(queue, [1, 'C'])

heapq.heappush(queue, [7, 'D'])

print (queue)

for index in range(len(queue)):

    print (heapq.heappop(queue))

출력 [ [1, ‘C’] , [5, ‘B’], [ 2, ‘A’], [7, ‘D’] ]

     [1, ‘C’ ]

        [2, ‘A’ ]

      [5, ‘B’ ]

      [7, ‘D’ ]

 

다익스트라 알고리즘

- 탐색할 그래프의 시작 정점과 다른 정점들간의 최단 거리 구하기

 

mygraph = {

    'A': {'B': 8, 'C': 1, 'D': 2},

    'B': {},

    'C': {'B': 5, 'D': 2},

    'D': {'E': 3, 'F': 5},

    'E': {'F': 1},

    'F': {'A': 5}

}

 

import heapq

 

def dijkstra(graph, start):

   

    distances = {node: float('inf') for node in graph}

    distances[start] = 0

    queue = []

    heapq.heappush(queue, [distances[start], start])

   

    while queue:

        current_distance, current_node = heapq.heappop(queue)

       

        if distances[current_node] < current_distance:

            continue

           

        for adjacent, weight in graph[current_node].items():

            distance = current_distance + weight

           

            if distance < distances[adjacent]:

                distances[adjacent] = distance

                heapq.heappush(queue, [distance, adjacent])

               

    return distances

dijkstra(mygraph, 'A')

출력 : { ‘A’ : 0 , ‘B’: 6 , ‘C’ : 1, ‘D’: 2, ‘E’: 5, ‘F’: 6}

 

참고: 최단 경로 출력

- 탐색할 그래프의 시작 정점과 다른 정점들간의 최단 거리 및 최단 경로 출력하기

 

 

import heapq

 

# 탐색할 그래프와 시작 정점을 인수로 전달받습니다.

def dijkstra(graph, start, end):

    # 시작 정점에서 각 정점까지의 거리를 저장할 딕셔너리를 생성하고, 무한대(inf)로 초기화합니다.

    distances = {vertex: [float('inf'), start] for vertex in graph}

 

    # 그래프의 시작 정점의 거리는 0으로 초기화 해줌

    distances[start] = [0, start]

 

    # 모든 정점이 저장될 큐를 생성합니다.

    queue = []

 

    # 그래프의 시작 정점과 시작 정점의 거리(0)을 최소힙에 넣어줌

    heapq.heappush(queue, [distances[start][0], start])

 

    while queue:

       

        # 큐에서 정점을 하나씩 꺼내 인접한 정점들의 가중치를 모두 확인하여 업데이트합니다.

        current_distance, current_vertex = heapq.heappop(queue)

       

        # 더 짧은 경로가 있다면 무시한다.

        if distances[current_vertex][0] < current_distance:

            continue

           

        for adjacent, weight in graph[current_vertex].items():

            distance = current_distance + weight

            # 만약 시작 정점에서 인접 정점으로 바로 가는 것보다 현재 정점을 통해 가는 것이 더 가까울 경우에는

            if distance < distances[adjacent][0]:

                # 거리를 업데이트합니다.

                distances[adjacent] = [distance, current_vertex]

                heapq.heappush(queue, [distance, adjacent])

   

    path = end

    path_output = end + '->'

    while distances[path][1] != start:

        path_output += distances[path][1] + '->'

        path = distances[path][1]

    path_output += start

    print (path_output)

    return distances

 

# 방향 그래프

mygraph = {

    '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(mygraph, 'A', 'F'))

F -> E -> D -> A

{ ‘A’ :[0, ‘A’], ‘B’: [6, ‘C’], ‘C’: [1. ‘A’], ‘D’: [2, ‘A’], ‘E’ : [5, ‘D’], ‘F’: [6, ‘E’] }

 

5. 시간 복잡도

- 위 다익스트라 알고리즘은 크게 다음 두 가지 과정을 거침

  - 과정1: 각 노드마다 인접한 간선들을 모두 검사하는 과정

  - 과정2: 우선순위 큐에 노드/거리 정보를 넣고 삭제(pop)하는 과정

 

- 각 과정별 시간 복잡도

  - 과정1: 각 노드는 최대 한 번씩 방문하므로 (첫 노드와 해당 노드간의 갈 수 있는 루트가 있는 경우만 해당), 그래프의 모든 간선은 최대 한 번씩 검사

    - 즉, 각 노드마다 인접한 간선들을 모두 검사하는 과정은 O(E) 시간이 걸림, E 는 간선(edge)의 약자

  - 과정2: 우선순위 큐에 가장 많은 노드, 거리 정보가 들어가는 경우, 우선순위 큐에 노드/거리 정보를 넣고, 삭제하는 과정이 최악의 시간이 걸림

    - 우선순위 큐에 가장 많은 노드, 거리 정보가 들어가는 시나리오는 그래프의 모든 간선이 검사될 때마다, 배열의 최단 거리가 갱신되고, 우선순위 큐에 노드/거리가 추가되는 것임

    - 이 때 추가는 각 간선마다 최대 한 번 일어날 수 있으므로, 최대 O(E)의 시간이 걸리고, O(E) 개의 노드/거리 정보에 대해 우선순위 큐를 유지하는 작업은 O(log{E}) 가 걸림

      - 따라서 해당 과정의 시간 복잡도는  O(Elog{E})

총 시간 복잡도

  - 과정1 + 과정2 = O(E) +  O(Elog{E})   =  O(E + Elog{E}) = O(Elog{E})

 

 

강의에 대해 정확하게 알고 싶다면 

https://bit.ly/2FgOONG