다익스트라 알고리즘

1. 최단경로 문제란?

* 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제이다.
* 가중치그래프( Weight Graph ) 에서 간선(Edge)의 가중치 합이 최소가 되도록하는 경로를 찾는것이 목적이다.

최단 경로 문제 종류

1. 단일 출발 및 단일 도착 최단 경로 문제

   • 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제

2. 단일 출발 최단 경로 문제

   • 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제

     따지고 보면 굉장히 헷깔릴 수 있으므로 명확히 하자면, 예를 들어 A,B,C,D 라는 노드를 가진 그래프에서 특정 노드를 A 라고 한다면, A외 모든 노드인 B,C,D 각 노드와 A 간에 (즉, A-B, A-C, A-D) 각각 가장 짧은 경로를 찾는 문제를 의미한다.

3. 전체 쌍(all-pair) 최단 경로: 그래프 내의 모든 노드쌍(u,v) 에 대한 최단 경로를 찾는 문제

2. 최단 경로 알고리즘 - 다익스트라 알고리즘

• 다익스트라 알고리즘은 위의 최단 경로 문제 종류중, 2번에 해당
  • 하나의 정점에서 다른 모든 정점간의 각각 가장 짧은 거리를 구하는 문제

다익스트라 알고리즘 로직

• 첫 정점을 기준을 연결되어있는 정점들을 추가해가며, 최단거리를 갱신하는 기법

• 다익스트라 알고리즘은 너비우선탐색(BFS)과 유사

  • 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점으로부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트

    다익스트라 알고리즘의 다양한 변형 로직이 있지만, 가장 개선된 우선순위 큐를 사용하는 방식에 집중해서 설명하기로함.

• 우선순위 큐를 활용한 다익스트라 알고리즘

  • 우선순위 큐는 MinHeap 의 방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 된다.

  1) 첫 정점을 기준으로 배열을 선언해 첫 정점에서 각 정점까지의 거리를 저장

  -   초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장함(inf)
  -   우선순위 큐에 (첫 정점, 거리 0)만 먼저 넣음  

  2) 우선순위 큐에서 노드를 꺼냄

      -   처음에는 첫 정점만 저장되어있으므로, 첫 정점이 꺼내짐.
      -   첫 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어있는 첫 정점에서 각 정점까지의 거리를 비교한다.
      -   배열에 저장된 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧은 경우, 배열에 해당 노드의 거리를 업데이트한다.
      -   배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다.
          -   결과적으로 너비우선탐색방식과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문하게된다.
          -   만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다, 더 긴 거리(루트)를 가진, (노드, 거리)의 경우에는 해당 노드와 인접한 노드간의 거리 계산한다.  

  3) 2번의 과정을 우선순쉬 큐에서 꺼낼 노드가 없을때까지 반복한다.

---

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)

# [[1,'C'], [5,'B'], [2,'A'], [7, 'D']]

for index in range(len(queue)):
    print(heapq.heappop(queue))
    # [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]) # start node 거리 0 을 우선순위 큐로 넣는다.

    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, [distances,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'))

5. 시간 복잡도

• 위 다익스트라 알고리즘은 크게 다음 두 가지 과정을 거친다.
  • 과정1: 각 노드마다 인접한 간선들을 모두 검사하는 과정
  • 과정2: 우선순위 큐에 노드, 거리 정보를 넣고 삭제(pop)하는 과정
• 각 과정별 시간 복잡도
  • 과정1: 각 노드는 최대 한 번씩 방문하므로 그래프의 모든 간선은 최대 한 번씩 검사
    • 즉, 각 노드마다 인접한 간선들을 모두 검사하는 과정은 O(E) 시간이 걸림, E는 간선(edge)의 약자.
  • 과정2: 우선순위 큐에 가장 많은 노드, 거리 정보가 들어가는 경우, 우선순위 큐에 노드, 거리 정보를 넣고, 삭제하는 과정이 최악의 시간이 걸림
    • 우선순위 큐에 가장 많은 노드, 거리 정보가 들어있는 시나리오는 그래프의 모든 간선이 검사될때마다 배열의 최단 거리가 갱신되고, 우선순위 큐에 노드, 거리는 추가되는 것이다.
    • 이 때 추가는 각 간선마다 최대 한 번 일어날 수 있으므로 최대 O(E)의 시간이 걸리고 , O(E) 개 의 노드 , 거리 정보에 대해 우선순위 큐를 유지하는 작업은 O( logE) 가 걸린다.

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

총 시간 복잡도

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

참고: 힙의 시간 복잡도

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