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

최단 경로 문제란?

• 두 노드를 잇는 가장 짧은 경로를 찾거나
• 가중치가 있는 그래프(Weighted Graph)에서 간선의 가중치의 합이 최소가 되도록 하는 경로를 찾으려는 것이 목적

 

최단 경로 문제 종류

1. 단일 출발 및 단일 도착 (single-source and single-destination shortest path problem) 최단 경로 문제
   1. 그래프 내의 특정 노드 u 에서 출발, 또다른 특정 노드 v 에 도착하는 가장 짧은 경로를 찾는 문제
2. 단일 출발 (single-source shortest path problem) 최단 경로 문제
   1. 그래프 내의 특정 노드 u 와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제따지고 보면 굉장히 헷깔릴 수 있으므로 명확히 하자면, 예를 들어 A, B, C, D 라는 노드를 가진 그래프에서 특정 노드를 A 라고 한다면, A 외 모든 노드인 B, C, D 각 노드와 A 간에 (즉, A - B, A - C, A - D) 각각 가장 짧은 경로를 찾는 문제를 의미함
3. 전체 쌍(all-pair) 최단 경로: 그래프 내의 모든 노드 쌍 (u, v) 에 대한 최단 경로를 찾는 문제

 

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

위의 종류 중 2번에 해당하는 것으로 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 것이다.

 

가장 짧은 거리인 최단거리를 갱신하는 법

• 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며한다

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

• 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트 (우선순위 큐를 사용하는 방식으로 알아보자)

 

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

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

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

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

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

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

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

 

배열 하나를 만들어 놓고 우선순위 큐를 이용하여 만들어 놓은 배열에 넣는다.

그러면 우선순위 큐에 의해 Weight가 오름차순 순서대로 정렬이 되면서 배열에 넣어지게 된다. 이 과정이 MinHeap방식을 이용해서 하게 된다는 것이다.

graph에 해당하는 가중치 그래프를 사전으로써 선언하고 dijkstra라는 함수를 통해 최단 거리를 찾아내게 되는 것이다.

패스트 캠퍼스

 

파이썬 구현

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']}
'''

 

시간 복잡도

두 가지 과정을 거침

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

• 과정1 + 과정2 = O(E) + O(ElogE) = O(E+ElogE)=O(ElogE)