[알고리즘] 다익스트라 알고리즘 + Python 구현

참조 : https://youtu.be/HFapeLxvdNg

 

---

Dijkstra(다익스트라) 알고리즘은 그래프에서 노드 간 최단 경로를 찾는 알고리즘입니다. 

그 방법을 간단한 5개의 노드를 가진 간단한 그래프를 통하여 단계별로 진행해보겠습니다.

 

---

현재 노드 : A

첫 번째로 일단 경로가 시작되는 노드를 잡습니다. 이 그래프에서는 A 노드가 되고 목적지 노드는 E로 가정합니다.

현재 노드에서 모든 노드까지의 비용을 계산합니다. 다만 현재의 노드와 바로 연결되지 않는 노드는 비용을 ∞로 둡니다.

A 아래의 4개의 노드는 [B] A / 3이라면 현재까지의 B 노드로 가는 최저 비용의 경로는 3의 비용을 가지고 있으며

바로 직전의 노드는 A 였음을 뜻합니다.

계산이 종료되었다면 지금까지 밝혀진 경로 4개의 노드 중 가장 낮은 비용을 가진 경로, 노드 C로 갑니다.

 

현재 노드 : C 

이전 단계에서 가장 낮은 비용을 가지고 있던 C 노드로 현재 노드가 옮겨졌습니다. 그렇다면 이제 다시 C와 연결된 

경로들을 탐색하여 최저 비용을 가진 경로를 찾아냅니다. 다만 이전 단계와 다른 점은 

이전에 지나갔던 노드는 다시 돌아가지 않습니다. 그렇기 때문에 A로 가는 경로(= 지나온 경로)는 제외됩니다.

그렇게 계산된 경로는 노드 이름 : 총비용으로 나열하면 B : 2, D : 5, E : ∞입니다. 

만약 E 노드처럼 요번에도 가는 경로가 발견되지 않았거나 더 높은 비용이라면 이전의 비용을 그대로 받아옵니다. 

만약 B 노드와 C 노드 사이의 비용이 3이었다면 총비용이 4가 되어 B 노드의 비용은 그대로 3이 되는 것입니다.

3개의 노드가 계산되었으니 요번에도 3개 중 가장 낮은 비용의 노드 B로 갑니다.

 

현재 노드 : B

B 노드에 와서 E까지의 비용이 밝혀졌습니다. 하지만 D까지의 경로가 더 비용이 낮은 것을 확인할 수 있습니다.

다시 D 노드로 이동합니다. 

 

현재 노드 : D

D를 경유하는 E까지의 노드는 B를 경유하여 E로 가는 경로보다 비용이 낮습니다. 

따라서 E까지의 경로는 현재 가장 낮은 경로인 A - C - D - E의 비용인 6으로 업데이트합니다.

 

현재 노드 : E

더 이상 탐색할 노드가 없으므로 최종 루트는 A - C - D - E 가 됩니다.

여기서 확인할 점은 최종 목적지 E까지 왔을 때 이전 노드를 차례대로 따라가면 그것이 최단 경로가 된다는 것입니다.

[E] D / 6 에서 D, [D] C / 5 에서 C, [C] A / 1에서 A 이렇게 따라가면 최단 경로가 나옵니다.

 

이제 다익스트라 알고리즘의 개념은 알게된 것 같습니다. 그렇다면 파이썬으로 구현해보도록 하겠습니다.

---

import heapq
import sys

start = 1
graph = [
    [1, 2, 3],
    [1, 3, 1],
    [3, 2, 1],
    [2, 5, 5],
    [3, 4, 4],
    [4, 5, 1] 
]


def Dijkstra(start, graph):
    
    nodes = {x:sys.maxsize for x in range(1,6)}
    
    nodes[start] = 0
    queue = []
    
    heapq.heappush(queue, [nodes[start], start])
    
    while queue:
        
        current_distance, current_node = heapq.heappop(queue)
        
        if nodes[current_node] < current_distance:
            continue
        
        for link in [x for x in graph if current_node in x[:2]]:
            temp = link.copy()
            temp.remove(current_node)
                        
            next_node = temp[0]
            distance = temp[1] + current_distance
            
            if distance < nodes[next_node]:
                nodes[next_node] = distance
                heapq.heappush(queue, [distance, next_node])
            
    return nodes

print(Dijkstra(1, graph))