자료구조&알고리즘

[알고리즘] 최단 경로 - 다익스트라

파송송 2022. 11. 21. 21:38
728x90

최단 경로

  • 최단 경로 문제는 두 노드를 잇는 가장 짧은 경로를 찾는 문제
  • 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

최단 경로 문제 종류

  • 단일 출발 및 단일 도착 (single-source and single-destimation shortest path problem) 최단 경로 문제
    • 그래프 내의 특정 노드 u에서 출발, 또 다른 특정 노드 V에 도착하는 가장 짧은 결로를 찾는 문제
  • 단일 출발 (single-source shortest path problem) 최단 경로 문제
    • 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제
  • 전체 쌍 (all-pair) 최단 경로
    • 그래프 내의 모든 노드 쌍(u, v)에 대한 최단 경로를 찾는 문제

다익스트라

  • 단일 출발 최단 경로 문제에 쓰이는 알고리즘
  • 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법
  • 너비우선탐색(BFS)와 유사함

우선순위 큐 다익스트라

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

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

     초기에는 첫 정점의 거리를 0으로, 나머지는 무한대로 저장함(inf)

     우선순위 큐에 (첫 정점, 거리 0)만 먼저 넣음

 

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

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

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

코드 구현

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}

시간복잡도

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

1. 그래프의 모든 간선은 최대 한번씩 검사함 \( O(E) \) E: 간선(edge)

2. 우선순위 큐에 모든 노드, 거리 정보가 들어가는 경우가 최악의 경우임

     각 간선마다 최대 한번 일어나기에 \( O(E) \), 노드/ 거리 정보에 대해 우선순위 큐를 유지하는 작업 \( O(logE) \)

-> \( ElogE\)

 

총 시간복잡도 = \( O(ElogE) \)

 

 

 

 

728x90