[Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드

저를 가장 오랫동안 괴롭혔던 알고리즘 중에 하나인 데이크스트라 알고리즘에 대해서 정리를 해볼까합니다. 그 때의 헤매던 저와 비슷한 분들께 도움이 되면 좋겠네요.

 

데이크스트라(Dijkstra) 최단 경로 알고리즘

최단 경로라는 말에서 짐작할 수 있듯이 데이크스트라 알고리즘은 출발점에서 도착점까지 가장 빠르게 갈 수 있는 경로를 탐색하는 알고리즘입니다. 최단 경로를 구하는 알고리즘에는 대표적으로 데이크스트라, 플로이드-워셜, 벨만-포드, A*(에이 스타) 이렇게 네가지가 있으며 이번 포스팅에서는 데이크스트라 알고리즘에 대해서만 정리를 해보겠습니다.

 

알고리즘의 이름인 데이크스트라는 알고리즘의 고안자인 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라(Edsger Dijkstra)의 이름을 따서 부르고 있습니다. 한국에서는 '데이크스트라' 보다는 '다익스트라'로 좀 더 잘 알려져있는데요. Dijkstra를 미국식으로 읽게 되면 다익스트라가 됩니다. 처음에 어떻게 퍼지게 되었는지는 모르겠지만 한국인은 보통 네덜란드어 보다는 영어가 더 익숙하니까 자연스럽게 다익스트라로 읽게 된게 아닐까 생각합니다. 따라서 어떻게 부르든지 의미는 통합니다만, 저는 데이크스트라라고 부르고 적도록 하겠습니다. 네덜란드 이름이니 네덜란드식으로 부르는게 맞다고 생각해서요.

 

데이크스트라 알고리즘의 과정

보통 최단 경로 문제는 그래프의 형태로 주어집니다. 당연하다면 당연한 것이지만 출발, 도착, 거리의 세 종류 입력이 필요하기 때문에 그래프로 생각하는 것이 가장 효율적이죠. 이런 최단 경로 문제들 중에서도 데이크스트라 알고리즘은 '특정 하나의 노드에서 다른 모든 노드까지의 최단 거리'를 구하는 것에 이점이 있습니다. 과정과 코드를 보면서 왜 그런 것인지 한 번 생각해봅시다.

 

1. 시작 노드를 정한다.

2. (시작 노드에서 다른 노드까지의) 최단 거리 배열을 초기화한다.

3. 현재 노드에서 아직 방문하지 않은 노드 중, 가장 가까운 노드를 선택한다.

4. 현재 노드의 거리값과 가까운 노드까지의 거리를 더해서 배열을 갱신하고 방문 처리 한다.

5. 모든 갈 수 있는 노드를 다 방문할 때까지 반복한다.

 

INF = 987654321  # any big number that over the input limit
    
def dijkstra(vertex, edges, start, end): # 1. set the start node.
    
    def get_nearest_node():
        min_distance = INF
        nearest_node = 0
        for i in range(1, vertex+1):
            if distance[i] < min_distance and visited[i] == False:
                nearest_node = i
        return nearest_node
    
    distance = [INF for _ in range(vertex+1)] # 2. initialize the distance array.
    visited = [False for _ in range(vertex+1)]
    distance[start] = 0
    for _ in range(vertex):
        cur_node = get_nearest_node() # 3. select the nearest node.
        visited[cur_node] = True
        for next_node, next_distance in edges[cur_node]:
            if distance[cur_node]+next_distance < distance[next_node]:
                distance[next_node] = distance[cur_node]+next_distance # 4. update min distance
    return distance[end]

 

edges는 이번 코드에서는 인접리스트로 간선 정보를 전달합니다. 다른 형태로 입력이 주어질 때는 그걸 가공해서 인접리스트로 만들면되겠죠.

 

과정 3을 보면 '현재 노드에서 갈 수 있는 노드 중 가장 가까운 노드를 선택한다' 라고 되어있습니다. 이 가장 가까운 노드를 선택한다는 부분이 데이크스트라를 그리디 알고리즘(순간 순간 최적의 값을 선택)의 일종이라고 분류하는 이유입니다. 이 덕분에 '나중에 좀 더 연결 노드는 같고 길이가 짧은 값이 나오면 어떡하지'하는 문제를 미연에 방지할 수 있죠. 애초에 가장 가까운 곳 부터 탐색하니까요. 그에 따라 이미 최단거리가 구해진 노드를 다시 탐색할 이유가 없기에 방문처리를 하게 됩니다.

 

과정 4와 코드를 보면 알 수 있듯이 데이크스트라 알고리즘에서 배열의 값을 갱신할 때는 이미 최단거리로 계산되어있는 노드의 정보를 활용합니다. 자연스레 모든 노드의 방문을 끝내면 시작 노드에서 다른 모든 노드까지의 최단거리가 계산이 되어 distance 배열에 저장이 되어있는 것이죠. 각 노드까지의 최단거리를 저장하다보니 시작 노드에서 임의의 다른 노드까지의 거리를 바로 확인할 수 있는 이점이 있고 이런 문제 유형에 사용하기 좋습니다.

 

위의 두 가지 특징으로 인해 데이크스트라는 모든 간선을 탐색하지만 이미 최단거리가 확정되어 있다면 해당 노드에 대해 연산을 하지 않고 이미 계산된 값을 사용해서 BFS와 같은 알고리즘에 비해 연산량이 적다는 장점이 생깁니다(사실 간선의 가중치가 없다면 BFS와 크게 다른 부분이 없긴 합니다만...).

 

개선된 데이크스트라 알고리즘의 과정

기존의 데이크스트라 알고리즘은 다음으로 탐색할 노드를 정하기 위해서 다음 노드 후보들 중에서 가장 가까운 노드를 정하는 과정을 매번 반복해야 했습니다. 운좋게 간선이 별로 없다면 상관없겠지만 나 자신을 제외한 모든 노드에 다 간선이 있다면 시간복잡도가 O(V^2) 정도 되었겠죠(정확하게는 (V-1)^2입니다만, Big O 표기법은 가장 높은 차수만 표현하기 때문에 V^2이라고 적습니다). 그래서 최단 거리 노드를 찾는 과정을 보다 효율적으로 하기 위해 우선순위큐에 다음에 탐색할 노드를 저장하는 방식이 생겼습니다(다음에 우선순위큐에 대한 내용을 다시 정리해서 올리도록 하겠습니다).

 

우선순위큐는 우선순위가 높은 자료부터 빼낼 수 있는 구조를 가진 자료형입니다. 보통 힙 트리로 구현하는데 힙의 특징이 가장 작은 값이나 가장 큰 값을 빠르게 찾고 추출하는 것이 용이하기 때문입니다. 가장 작은 값을 빨리 찾을 수 있다고 하니 뭔가 감이 오실텐데요. 최단거리를 기준으로 하는 우선순위큐에 다음에 탐색할 노드를 저장한다면 최단거리 노드를 찾는 시간을 줄일 수 있을 것 같습니다. 실제로 우선순위큐를 이용한 데이크스트라 알고리즘은 최악의 경우에도 O(ElogV)의 시간복잡도를 보장합니다. 힙 트리에 자료를 삽입하거나 삭제하는 시간이 logV만큼 걸리고 그걸 최대 간선횟수만큼 반복하니까 ElogV가 나오는 것입니다.

 

세부적인 수행과정이 달라졌을 뿐, 전체적인 과정은 크게 다르지 않습니다.

 

import heapq

INF = 987654321  # any big number that over the input limit

def improved_dijkstra(vertex, edges, start, end):
    h = []
    heapq.heappush(h, (0, start))
    distance = [INF for _ in range(vertex+1)] # 2. initialize the distance array.
    distance[start] = 0
    while h:
        cur_distance, cur_node = heapq.heappop(h) # 3. select the nearest node.
        if cur_distance < distance[cur_node]:
            continue
        for next_node, next_distance in edges[cur_node]:
            if distance[cur_node]+next_distance < distance[next_node]:
                distance[next_node] = distance[cur_node]+next_distance # 4. update min distance
                heapq.heappush(h, (distance[next_node], next_node))
    return distance[end]

 

데이크스트라 알고리즘의 한계

사실 데이크스트라가 완벽하게 일반화된 최단 경로 알고리즘이라면 다른 최단 경로 알고리즘을 굳이 알 필요도 사용하지도 않을텐데, 이렇게 여러가지가 있는 걸 보면 데이크스트라 알고리즘이 모든 상황에 사용가능한 건 아닌 것 같다는 생각이 들죠. 들어보셨을지도 모르겠지만 '음의 간선이 존재할 경우 데이크스트라 알고리즘을 사용할 수 없다'는 한계가 존재합니다. 정확하게 말하자면 데이크스트라 알고리즘의 구조적인 특징 때문에 결과가 잘못 나올 가능성이 있습니다. 제가 예시로 사용할 그래프 그림이랑 함께 볼까요. 개선된 데이크스트라 알고리즘을 이용하는 것으로 생각해보겠습니다.

 

 

위에서 봤던 데이크스트라의 과정을 떠올리면서 한 번 1에서 3으로 가는 최단거리를 한 번 구해볼까요.

 

distance = [INF, INF, INF] , h = [(0, 1)]

시작 노드 : 1

distance = [0, INF, INF], h = []

1에서 가장 가까운 노드 : 3, 거리 : 3, 0 + 3 < INF : 우선 순위 큐에 추가

distance = [0, INF, 3], , h = [(3, 3)]

1에서 가장 가까운 노드 : 2, 거리 : 5, 0 + 5 < INF : 우선 순위 큐에 추가

distance = [0, 5, 3], h = [(3, 3), (5, 2)]

더 이상 1에서 방문 가능한 노드 없음, 우선 순위 큐에서 원소 추출

출발 노드 : 3

distance = [0, 5, 3], h = [(5, 2)]

더 이상 3에서 방문 가능한 노드 없음, 우선 순위 큐에서 원소 추출

출발 노드 : 2

distance = [0, 5, 3], h = []

2에서 가장 가까운 노드 : 3, 거리 : -4, 5 - 4 < 3 : 우선 순위 큐에 추가

disitance = [0, 5, 1], h = [(1, 3)]

출발 노드 : 3

distance = [0, 5, 1], h = []

더 이상 3에서 방문 가능한 노드 없음, 우선 순위 큐에서 원소 추출

우선 순위 큐 원소 없음 : 코드 종료

결과 1

 

어라? 음의 간선이 있는데 제대로 된 결과가 나왔는데요? 맞습니다. 음의 간선이 있어도 맞는 결과가 나오는 경우도 있습니다. 그럼 사용 가능한 거 아닌가요? 같은 그래프에 이번엔 방향성이 없다고 생각을 해보겠습니다.

 

distance = [INF, INF, INF], h = [(0, 1)]

시작 노드 : 1

distance = [0, INF, INF], h = []

1에서 가장 가까운 노드 : 3, 거리 : 3, 0 + 3 < INF : 우선 순위 큐에 추가

distance = [0, INF, 3], h = [(3, 3)]

1에서 가장 가까운 노드 : 2, 거리 : 5, 0 + 5 < INF : 우선 순위 큐에 추가

distance = [0, 5, 3], h = [(3, 3), (5, 2)]

더 이상 1에서 방문 가능한 노드 없음, 우선 순위 큐에서 원소 추출

출발 노드 : 3

distance = [0, 5, 3], h = [(5, 2)]

3에서 가장 가까운 노드 : 2, 거리 : -4, 3 - 4 < 5 : 우선 순위 큐에 추가

distance = [0, -1, 3], h = [(-1, 2), (5, 2)]

3에서 가장 가까운 노드 : 1, 거리 : 3, 3 + 3 > 0 : 추가 안함

더 이상 3에서 방문 가능한 노드 없음, 우선 순위 큐에서 원소 추출

출발 노드 : 2

distance = [0, -1, 3], h = [(5, 2)]

2에서 가장 가까운 노드 : 3, 거리 : -4, -1 - 4 < 3 : 우선 순위 큐에 추가

disitance = [0, -1, -5], h = [(-5, 3), (5, 2)]

2에서 가장 가까운 노드 : 1, 거리 : 5, -1 + 5 > 0 : 추가 안함

더 이상 3에서 방문 가능한 노드 없음, 우선 순위 큐에서 원소 추출

출발 노드 : 3

...

 

이번에는 2와 3을 계속 왔다갔다하면서 무한반복하게됩니다. 에이, 이거 방문처리를 안해서 그런거잖아요. 개선된 데이크스트라도 미방문 노드를 기록하지 않을 뿐 방문처리를 합니다만, 그 주장도 완전히 틀린 말은 아닙니다. 그럼 기존의 데이크스트라처럼 방문처리를 해볼까요?

 

distance = [INF, INF, INF], visited = [False, False, False]

시작 노드 : 1

distance = [0, INF, INF], visited = [True, False, False]

1에서 가장 가까운 노드 : 3, 거리 : 3, 방문x : 우선 순위 큐에 추가

distance = [0, INF, 3], visited = [True, False, False]

1에서 가장 가까운 노드 : 2, 거리 : 5, 방문x : 우선 순위 큐에 추가

distance = [0, 5, 3], visited = [True False, False]

더 이상 1에서 방문 가능한 노드 없음, 우선 순위 큐에서 원소 추출

출발 노드 : 3

distance = [0, 5, 3], visited = [True, False, True]

3에서 가장 가까운 노드 : 2, 거리 : -4, 방문x : 우선 순위 큐에 추가

distance = [0, -1, 3], visited = [True, False, True]

3에서 가장 가까운 노드 : 1, 거리 : 3, 방문o : 추가 안함

더 이상 3에서 방문 가능한 노드 없음, 우선 순위 큐에서 원소 추출

출발 노드 : 2

distance = [0, -1, 3], visited = [True, True, True]

2에서 가장 가까운 노드 : 3, 거리 : -4, 방문o : 추가 안함(하지만 기존보다 거리 값이 작으므로 테이블은 갱신)

disitance = [0, -1, -5], visited = [True, True, True]

우선 순위 큐 원소 없음 : 코드 종료

결과 -5

 

아하~ 그럼 이번엔 갱신하면서 방문처리를... 이라고 생각했다면 곤란합니다. 지금이야 그래프를 간단하게 줬지만 엄청 복잡한 그래프가 주어지고 나중에 더 좋은 경로가 나왔을 때 이미 거리를 갱신하면서 방문체크를 했다면 최단거리로 갱신을 못하니까요. 방문처리는 현재 노드에서 더 이상 갈 노드가 없을 때 하는 겁니다.

 

과정을 직접 쓰는 시간이 너무 길었는데요. 다시 한 번 왜 지금 이걸 다 손으로 써가면서 하고 있었는지 상기시켜봅시다. '데이크스트라는 음의 간선이 있으면 정확한 결과가 나오지 않을 가능성이 있다' 라는 한계점이 존재한다고 말씀을 드렸습니다. 우리는 음의 간선이 있어도 제대로 된 결과가 나오는 경우와 음의 간선이 포함된 사이클을 돌면서 무한 루프를 도는 경우, 방문처리를 해주어도 최단 거리의 갱신과정에서 한 번 더 계산이 되면서 제대로 된 결과가 나오지 않는 경우를 확인했습니다(갱신과 함께 방문처리를 하는 것도 안된다고 했죠).

 

그래서 왜 이런 일이 발생하는걸까요? 정답은 최단 거리 갱신이 가능하면 일단 갱신을 하기 때문이라고 할 수 있겠습니다. 기존에 방문 처리가 되어있는 노드여도 더 짧은 거리로 갱신이 가능하다면 일단 갱신을 해버리기 때문이죠. 모든 간선이 양의 가중치를 갖는다면 크게 상관이 없는 부분입니다. 하지만 음의 가중치를 갖는 간선이 존재하고 최단 경로에 해당 간선이 포함이 된다면 알고리즘의 구조 상 음의 간선을 많이 통과하는 방향으로 움직이기 때문이죠.

 

그래서 데이크스트라는 이런 한계점이 존재하기 때문에 플로이드-워셜이나 벨만-포드와 같은 다른 최단 경로 알고리즘도 알아두어야 합니다. 이 알고리즘들도 언젠가 정리해서 알려드릴 날이 오면 좋겠네요.

 

데이크스트라는 그리디? 다이나믹 프로그래밍?

저도 예전에 많이 고민했던 부분입니다. 누구는 그리디라고 하고, 누구는 다이나믹이라고 하고... 그래서 그 때는 그냥 그 두개를 다 합쳤나보다하고 넘어갔었는데 공부를 좀 하다보니 이제는 그리디라고 보는게 맞다고 할 수 있을 것 같습니다.

 

데이크스트라는 그리디 알고리즘을 기반으로 합니다. 그리디 알고리즘은 순간 순간에 최적의 선택을 하는 알고리즘이라는 것을 알고계신다면 조금 설명이 편할 것 같은데요. 조금 더 풀어서 설명을 하면 '지금 하는 선택이 나중에 하는 선택에 영향을 미치지 않거나, 영향을 미치더라도 지금의 선택이 최적의 결과를 도출하는 알고리즘' 이라고 할 수 있을 것 같습니다. 뭔가 머리가 복잡해지는 것 같으니 자세한 건 다음에 그리디 알고리즘 포스팅을 하게 되면 거기서 설명하는 것으로 하고 일단은 데이크스트라로 넘어갑시다.

 

데이크스트라의 과정에서 현재 갈 수 있는 노드에서 가장 가까운 노드를 선택하는 것, 이 부분이 그리디를 기반으로 한다는 주장의 근거입니다. 지금 갈 수 있는 노드에서 제일 가까운 노드를 선택해서 거리를 갱신한다 하더라도, 나중에 하는 선택에 어떠한 영향도 미치지 않습니다. 어차피 더 짧은 경로가 나오면 다시 배열을 갱신하기 때문이죠. 또한 개선된 데이크스트라 알고리즘에서는 방문처리를 미방문 노드 번호로 저장하는 것이 아니라, 기존에 최단거리로 저장되어 있는 값보다 지금 계산한 값이 더 작다면 이미 방문했던 노드라도 다시 방문하기 때문에 상관 없습니다.

 

그렇다면 다이나믹 프로그래밍이 아닌 이유는 뭘까요? 결론부터 말하자면 '알고리즘의 구조적인 차이' 때문입니다. 데이크스트라와 다이나믹 프로그래밍의 차이를 말하기 전에 그리디와 다이나믹 프로그래밍의 차이를 먼저 보면 좀 좋을 것 같은데요. 그리디 알고리즘은 사실 동적 계획법의 비효율적인 부분 때문에 등장한 알고리즘입니다. 다이나믹 프로그래밍은 가능한 모든 방법을 다 고려한 다음 그 결과들 중에서 최적의 해를 구하는 특징을 가지고 있어서 연산량에 있어서 비효율적인 부분이 존재할 수 있습니다. 하지만 그리디는 순간 순간의 최적의 선택을 하기 때문에 최악의 경우에 다이나믹 프로그래밍과 연산량이 같게 되겠죠(위에서도 말했지만 순간의 최적의 해가 꼭 최적의 결과를 이끌어낸다는 보장은 없기에 항상 그리디를 써도 되는 건 아닙니다). 극단적으로 예를 들어서 1번에서 n번으로 가는 경로의 조합이 m개 있다고 치면 다이나믹 프로그래밍은 모든 경우를 다 해보겠지만, 그리디는 1번에서 a로 가는 최적의 값, a에서 b로 가는 최적의 값, ... 을 해서 최악의 경우 m개를 시도할 것이고 보통은 m개 보다 적은 경우만 시도하게 될 것입니다.

 

이 내용을 바탕으로 데이크스트라를 보면 한 번 방문이 끝난 노드는 더 이상 방문하지 않고 값만 활용하기 때문에 모든 경우를 다 시도해보는 일은 없겠죠. 따라서 다이나믹 프로그래밍 보다는 그리디 알고리즘이라고 보는게 맞을 것입니다. 하지만 다이나믹 프로그래밍을 사용하는 최단 경로 알고리즘이 없는 것은 아닙니다. 플로이드-워셜, 벨만-포드 알고리즘은 다이나믹 프로그래밍의 일종이라고 볼 수 있습니다.

 

그렇다면 왜 데이크스트라를 다이나믹 프로그래밍이라고 알고 있는 사람들이 있을까요? 저도 헷갈렸기 때문에 제가 그렇게 생각했던 이유를 말해보자면, 다이나믹 프로그래밍은 많은 경우를 시도하기 위해 다른 부분에서 시간 복잡도를 줄여야 할 필요가 있는데 그걸 위한 장치로 메모이제이션 기법을 사용하고 있습니다. 다만 1차원 배열을 사용하는 다이나믹 프로그래밍은 백준 사이트에서 낮은 난이도의 문제에 속하기 때문에 상대적으로 이런 저런 개념에 익숙하지 않은 상태에서 다이나믹 프로그래밍 문제를 만나게 되고 다이나믹 프로그래밍과 메모이제이션을 같은 말이라고 생각하게 되는게 착각의 시작이 아닌가 생각합니다.

 

저는 데이크스트라를 2차원 다이나믹 프로그래밍보다도 늦게 접했고 제가 배운 데이크스트라 알고리즘에서 메모이제이션을 사용했기 때문에 자연스럽게 다이나믹 프로그래밍의 일종이라고 생각했습니다. 메모이제이션 외에도 개념적으로 비슷한 부분이 있기도 했구요. 아무래도 혼자서 공부를 하다보면 누군가 한 사람이 쭉 설명해주는 내용을 보는 일 보다는 이 사람의 포스팅, 저 사람의 강의, 그 사람의 책 등등 같은 것에 대해 여러 사람이 알려주는 것을 듣고 보고 배우게 되는데요. 이런 과정 속에서 지식이 유기적으로 연결되지 않고 파편화되어 어 이런 말 들었던거 같은데, 어 이건 이렇다고 하지 않았나? 하면서 어설프게 알고 있는 지식들이 발목을 잡은게 아닌가 생각합니다. 물론 이건 어디까지나 제가 그랬다는 것이고 다른 분들은 또 다른 이유가 있을 수도 있겠죠.

 

그리고 데이크스트라가 다이나믹 프로그래밍을 기반으로 하지 않는다는 내용에 좀 더 힘을 실어주는 부분으로, 메모이제이션을 사용하지 않아도 데이크스트라 문제는 풀 수 있습니다. 거리를 저장하는 배열을 사용하지 않고 우선순위큐에 현재까지 이동한 거리도 함께 추가해서 풀면 되거든요(BFS 문제 중에 이렇게 거리도 큐에 추가해서 풀어야 하는 문제들이 종종 있습니다. 그거랑 같은 테크닉이에요). 메모이제이션도 안썼으니까 이젠 진짜 다이나믹 프로그래밍이라고 부를 수 없겠죠. 다만 따로 변수를 만들어서 저장해놓지 않는다면 모든 노드에 대한 최단거리는 알 수 없겠네요.

 

물론 완전히 고유한 물체에 이름을 붙이는 것이 아니라 해답을 위해 문제를 풀어나가는 과정에 이름을 붙여놨으니 이리 저리 맞물리거나 개념이 혼동되는 건 어떻게 보면 당연한 일이라고 생각합니다. 데이크스트라를 다이나믹이라고 말하는 사람들이 잘못되었다는 뜻은 아닙니다. 사실 그렇게 중요한 것도 아니구요. 그리디면 어떻고 다이나믹이면 어떻습니까. 물론 알고리즘 강의를 전문적으로 하고 싶은 분은 누구보다도 확실히 알아둬야겠죠. 그게 프로니까요.

 

데이크스트라 알고리즘의 사용 예시

사실 저도 실사용 예를 많이는 모릅니다. 최단 경로 알고리즘이다보니 내비게이션에서 경로 탐색을 해주는 알고리즘으로 사용된다는 부분은 많은 분들이 알고 계실겁니다. 물론 그대로 갖다 쓰는 건 아닐거고 이리저리 수정을 하겠지만요. 그 외에도 경로 탐색과 관련된 문제들이면 어지간하면 적용이 가능하지 않을까 생각이 드네요.

 

정리

마지막으로 총정리를 해봅시다. 데이크스트라 알고리즘은 그리디를 기반으로하는 최단 거리를 구하는 알고리즘입니다. 현재 노드에서 방문할 수 있는 가장 가까운 노드부터 거리를 갱신해가면서 최종적으로 모든 간선을 다 탐색하게 됩니다. 각 노드까지의 최단거리를 저장하고 해당 값을 불러서 계산하기 때문에 BFS에 비해서 연산량이 적습니다. 하지만 음의 간선이 최단 경로에 포함이 될 경우 정확한 결과가 나오지 않을 가능성이 있기 때문에 음의 간선이 존재할 때는 사용을 지양하는 편이 좋습니다. 그 이유는 최단거리로 갱신하고자 하는 알고리즘의 구조 상 음의 간선을 최대한 많이 통과하는 방향으로 움직이기 때문입니다.

 

어쩌다보니 코드나 코드에 대한 설명보다 글이 너무 많아진 것 같습니다. 그만큼 제가 데이크스트라에 대해 많이 고민을 했다는 증거가 아닌가 생각합니다.

 

References : 

동적 계획법 - 위키 백과

탐욕 알고리즘 - 위키 백과

데이크스트라 알고리즘 - 위키 백과

이것이 코딩테스트다 with 파이썬 - 나동빈