12. 알고리즘 고급 탐색, 최단 경로 알고리즘, 다익스트라 알고리즘

다익스트라

난이도 최상

1. 최단 경로 문제란?

최단 경로 문제란, 두 노드를 잇는 가장 짧은 경로를 찾는 문제다

가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적이다.

 

최단 경로 문제 종류

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

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

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

- 그래프 내의 특정 노드 u에서 출발해서, 그래프 내 모든 노드 각각에 도착하는 가장 짧은 경로를 찾는 문제

3. 전체 쌍 최단 경로 : 그래프 내의 모든 쌍에 대한 최단 경로를 찾는 문제

 

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

다익스트라 알고리즘은 위의 최단 경로 문제 종류 중, 2번에 해당한다.

하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 문제.

 

다익스트라 알고리즘 로직

첫 정점을 기준으로 연결되어있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법. 최단거리를 업데이트 하는 방법.

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

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

 

다익스트라 알고리즘의 우선순위 큐를 사용하는 방식

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

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

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

- 우선순위 큐에 (첫 정점, 거리 0)만 먼저 넣는다.

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

- 처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내진다.

- 첫 정점에 인접한 노드들 각각에 대해, 첫 정점에는 각 노드로 가는 거리와 현재 배열에 저장되어있는 첫 정점에서 각 정점까지의 거리를 비교한다.

- 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트 한다.

- 배열에 해당노드의 거리가 업데이트 된 경우, 우선순위 큐에 넣는다.

 - 결과적으로 너비 우선 탐색 방식과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문하게 된다.

 - 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다, 더 긴 루트를 가진 (노드, 거리)의 경우에는 해당 노드와 인접한 노드간의 거리계산을 하지 않는다.

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

 

 4. 파이썬으로 다익스트라 알고리즘 구현

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

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

 

import heapq

queue=[]
#heap 형태로 데이터 넣기
heapq.heappush(queue,[2,'a'])
heapq.heappush(queue,[5,'b'])
heapq.heappush(queue,[1,'c'])
heapq.heappush(queue,[7,'d'])

queue

결과

[[1, 'c'], [5, 'b'], [2, 'a'], [7, 'd']]

heap은 트리구조를 가지고 있기 때문에 우리 눈에 리스트가 완전히 sorting 된것 처럼 보이지는 않지만, 최소힙 즉 [1,'c']는 인덱스0에 잘 들어있는걸 알 수 있다. 

 

pop메서드로 하나씩 꺼내보면 최소힙을 만족시킨다.

for index in range(len(queue)) : 
    print(heapq.heappop(queue))

결과

[1, 'c']
[2, 'a']
[5, 'b']
[7, 'd']

 

구현

1. 초기화

import heapq

def dijkstra(graph,start) : 
    
    distances ={node:float('inf') for node in graph}
    distances[start]=0
    
    queue=[]
    
    heapq.heappush(queue,[distances[start],start])

distances라는 딕셔너리를 선언하여 시작 노드 부터 각 노드 간의 초기 거리 값을 매칭한다. (처음에는 다 inf 값, 무한대로 설정)

start, 즉 본인에서 출발해서 본인으로 오는 최단 거리는 0이므로 0으로 입력한다.

queue라는 리스트를 선언하여 우선순위 큐를 만든다. 

queue에 먼저 시작 노드를 넣는다. 

(queue는 리스트 앞에 있는 숫자로 우선순위를 정하기 때문에 리스트 앞쪽에 distance값을 넣는다) 

 

2. 구현

    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

while반복문.

queue에서 pop한 리스트 값을 각각 현재거리와 현재노드로 선언한다. 

만약에, distances에 이미 있는 거리가 queue에서 뽑은 현재거리보다 작으면 수행할 필요가 없기 때문에 continue를 걸어준다(우선순위 큐에는 초반에 들어간, 거리값이 큰 리스트도 들어가 있기 때문에.)

 

for문(queue에서 pop한 현재 노드에 인접해 있는 모든 노드까지의 거리를 더해보고, distances에 있는 거리와 비교하기 위해)

pop한 현재노드에 인접해 있는 노드들을 불러오기 위해 graph를 참고하여, 현재 노드에 인접한 노드들과 그 거리를 불러온다. 각각 인접한노드명, weight로 선언한다.

거리를 다시 계산해보기 위해 현재 거리에 현재노드에 인접한 노드까지의 거리를 더한다. 

만약 그 값이 distances에 저장되어있는 거리 보다 작으면 distances의 거리값을 갱신해준다.

그리고 그 값을 다시, queue에 넣는다. 

dijkstra(mygraph,'a')

결과

{'a': 0, 'b': 6, 'c': 1, 'd': 2, 'e': 5, 'f': 6}

 

결론

일단, 값을 queue에 집어넣는다는 것은 a와 그 노드가 중간에 어떤 노드들을 거쳐서 연결되어있다는 뜻이다. distances에 저장되어있는 값은 현재까지의 최단 경로인 것이고, 다른 노드를 거쳤을 때 그 값이 더 작으면, 최단 경로가 갱신되는 것이다. 

 

시간복잡도

다익스트라 알고리즘은 크게 두가지 과정을 거친다.

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

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

 

각 과정별 시간 복잡도

1. 각 노드는 최대 한번씩 방문하므로 (루트가 있는 경우) 그래프의 모든 간선은 최대 한번씩 검사한다. 

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

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

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

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

따라서 해당 과정의 시간 복잡도는 O(ElogE)

 

총 시간 복잡도

1+2 = O(E)+O(ElogE)=O(ElogE)