(알고리즘) 최단경로 알고리즘 - 다익스트라 알고리즘

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

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

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

우선순위큐는 최소힙 방식을 활용한다. 즉 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))

첫번째 print의 값은 [[1, 'C'], [5, 'B'], [2, 'A'], [7, 'D']] 이다. 정렬이 안되어있는 것처럼 보이지만 맨 앞 은 최소 값이며, 

두번재 print 값을 보면

[1, 'C']

[2, 'A']

[5, 'B']

[7, 'D']

이렇게 되는데, 최소힙 방식으로 pop을 할때마다 제일 최소값이 뽑혀 나오는 것을 알 수 있다. 

 

다익스트라 알고리즘

• 탐색할 그래프의 시작 정점과 다른 정점들간의 최단 거리 구하기
• 먼저 그래프를 자료구조화 시켜야 한다. 아래와 같다

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])  # 위의 예제에서 봤듯이, 앞에 먼저 밸류값, 즉 숫자를 넣어주고 뒤에 start, 즉 노드를 넣어줘야한다. 제일 처음에는 우선순위 큐에 0,A가 담긴다.
    
    while queue:
        current_distance, current_node = heapq.heappop(queue) #  이렇게 하면 queue의 제일 첫번째 값(디스턴스 최소값)의 밸류값이 current_distance에, 노드가 current_node에 들어간다.
        
        if distances[current_node] < current_distance:
            continue
            
        for adjacent, weight in graph[current_node].items(): # 만약 current_node가 A였다고하면, 그 item은 graph자료구조에서 A 키값의 밸류이다. 그중 B,C,D가 adjacent에 들어가고 가중치가 weight에 들어간다.
            distance = current_distance + weight
            
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])
                
    return distances

 

참고: 최단 경로 출력 (이건 혼자 한 번 해봐라)

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

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'))

 

 

5. 시간 복잡도

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

  • 과정1: 각 노드마다 인접한 간선들을 모두 검사하는 과정
  • 과정2: 우선순위 큐에 노드/거리 정보를 넣고 삭제(pop)하는 과정

• 각 과정별 시간 복잡도

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

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

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

    • 우선순위 큐에 가장 많은 노드, 거리 정보가 들어가는 시나리오는 그래프의 모든 간선이 검사될 때마다, 배열의 최단 거리가 갱신되고, 우선순위 큐에 노드/거리가 추가되는 것임
    • 이 때 추가는 각 간선마다 최대 한 번 일어날 수 있으므로, 최대 O(E)의 시간이 걸리고, O(E) 개의 노드/거리 정보에 대해 우선순위 큐를 유지하는 작업은 𝑂(𝑙𝑜𝑔𝐸)O(logE) 가 걸림
      • 따라서 해당 과정의 시간 복잡도는 𝑂(𝐸𝑙𝑜𝑔𝐸)O(ElogE)

총 시간 복잡도

• 과정1 + 과정2 = O(E) + 𝑂(𝐸𝑙𝑜𝑔𝐸)O(ElogE) = 𝑂(𝐸+𝐸𝑙𝑜𝑔𝐸)=𝑂(𝐸𝑙𝑜𝑔𝐸)O(E+ElogE)=O(ElogE)

참고: 힙의 시간 복잡도

• depth (트리의 높이) 를 h라고 표기한다면,
• n개의 노드를 가지는 heap 에 데이터 삽입 또는 삭제시, 최악의 경우 root 노드에서 leaf 노드까지 비교해야 하므로 h=log2n 에 가까우므로, 시간 복잡도는 O(logn)