[최단경로 알고리즘] Dijkstra Algorithm

본 포스팅은 한동대학교 최혜봉 교수님 강의 자료를 참고했음을 밝힙니다. 

 

 

최단 경로라는 것은 출발지에서 목적지까지 가는 경로에서 가장 비용이 적게 드는 최적 경로를 계산하는 것을 의미한다.

다음 피피티 슬라이드를 참고해보자

출처 : 최혜봉 교수님 강의자료

 

우선 최단 경로라는 것은 여러 특징들을 바탕으로 하는데

1. 하나의 최단 경로 내 부분 경로는 자체로 최단 경로를 이룬다.

2. 하나의 vertex에서 다른 vertex로 가는 최단 경로로 구성된 트리들이 있다. 

 

이 2가지 특징이 기본으로 전제가 된다.

 

1번은 어떠한 것을 의미하냐면

예를 들어 A->B가 최단 경로라고 한다면, 

A -> x

x -> y

y -> B라고 하면

A -> x, x -> y, y -> B 각각도 최단 경로가 됨을 의미한다. 

 

그렇다면 여기서 중요한 것은 또한 최단경로로 이루어진 트리는 Spanning 트리가 되는데

이 Spanning Tree는 다음 구조를 만족한다.

(1) 모든 vertex를 포함해야 한다

(2) 모든 vertex는 다 connected

(3) Cycle이 존재하면 안됨

 

 

그렇다면 이러한 경로를 어떻게 효율적으로 찾을 수 있을까.

최단 경로를 찾는 알고리즘은 많은데 본 포스팅에서는 이 중 대표적으로 Non-negative Undirected Graph에서 대표적으로 사용되는 알고리즘인 다익스트라 알고리즘에 대해 살펴보도록 하겠다.

 

출처 : 최혜봉 교수님 강의자료

 

이러한 다익스트라 알고리즘은 중요한 전제가 있는데, 

[1] 그래프는 Connected 되어 있어야 한다.

[2] 모든 edge들은 Undirected여야 한다.

[3] 모든 edge들의 weight는 non-negative여야 한다. 

 

그리고 다익스트라는 최단 경로를 구한 녀석은 'Cloud'라는 곳에 저장을 해 놓는데, 이 클라우드에는 최단 경로를 저장해놓으며 최단 경로를 찾을 때마다 업데이트가 되는 값이다. 

 

그렇다면 이 업데이트는 어떻게 이루어질까?

여기서 가장 중요한 개념은 바로 'Edge Relaxation'이다

 

출처 : 최혜봉 교수님 강의자료

 

위 피피티에도 나와있지만

d(z) <- min{d(z), d(u)+weight(e)}

이 수식이 바로 edge relaxation의 핵심이다. 

 

구체적으로 그림이 무엇인지 살펴보자

출처 : 최혜봉 교수님 강의자료

위 그림에서 d(u)까지는 현재 최단 경로가 정해져서 클라우드 안에 있고 다음 z 노드를 바라보고 있는 상황이다. 

현재 d(z)값은 75로 되어 있지만 cloud에서 나아가는 경로를 보니 60이라는 보다 비용이 적은 경로를 발견하고 d(z) = 60으로 값을 변경하고 클라우드 안에 추가되는 방식으로 동작을 하게된다.

 

그렇다면 이를 구체적인 예시를 통해 분석해보자

출처 : 최혜봉 교수님 강의자료

 

우선 다음과 같은 예제가 있을 때, 

 

vertex와 경로 값을 가지고 있는 우선순위 큐를 구축한다.

초기의 출발 vertex값은 경로가 0(자기 자신이므로), 나머지 vertex들의 경로는 무한대로 설정한다. 

 

그리고 2가지의 과정을 우선순위 큐가 empty할 때까지 반복하는데 

1. 우선순위 큐에서 경로가 가장 짧은 vertex를 pop, 이를 u로 설정한다.

2. u와 connect 되어 있는 vertex들 d값 갱신

 

이제 이 논리를 가지고 예제를 풀어보자

출처 : 최혜봉 교수님 강의자료

 

A부터 출발을 하면, 

u=A가 되고 A와 연결된 B, C, D에 대해 최단 경로를 업데이트한다.

위 그림의 경우 B의 예시를 보여주는데

B의 경우 초기 d(B)가 무한대로 되어 있었는데 최소 경로인 8로 업데이트를 시켜준다. 

C, D도 마찬가지의 과정을 거쳐준다. 

출처 : 최혜봉 교수님 강의자료

 

다시 루프를 돌아 다음 우선순위 큐에서 경로가 가장 작은 C를 추출하고, C와 연결되어 있는 vertex의 d값을 갱신한다.

예를 들어 d(D)는 현재 4로 되어 있는데

C에서 업데이트를 하면

d(D) = min(d(D), d(C)+weight(C,D)) 를 통해 d(D) = 3으로 업데이트 되므로 수정이 된다.

이렇게 E, F 마찬가지로 다 업데이트가 이루어진다.

 

그리고 위와 마찬가지 과정을 반복 수행하여 큐가 빌 때까지 수행해준다. 

 

이를 수행하는 예제 코드는 다음과 같다. 

출처 : https://justkode.kr/algorithm/python-dijkstra

import heapq

graph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

def dijkstra(graph, start) :
    ## start로부터 거리값 초기 setting
    distance = { node : float('inf') for node in graph }
    distance[start] = 0 # 시작 값은 0
    queue = []
    heapq.heappush(queue, [distance[start], start])

    while queue :
        current_dist, current_dest = heapq.heappop(queue)

        ### 기존에 있는 거리보다 길다면, 볼 필요가 없음
        if distance[current_dest] < current_dist :
            continue

        for new_dest, new_dist in graph[current_dest].items() :
            dist = current_dist + new_dist
            if dist < distance[new_dest] :
                distance[new_dest] = dist
                heapq.heappush(queue, [dist, new_dest])
    return distance

print(dijkstra(graph, 'A'))

 

Time Complexity는 어떻게 될까

출처 : 최혜봉 교수님 강의자료

 

m = edge의 수, n = vertex의 수라고 할 때

모든 vertex들의 edge 수의 합은 2m이 된다. 

 

우선순위 큐에서 remove min을 해주는 연산이 logn이므로

2m*logn 즉, O(mlogn)이 된다.