[알고리즘] 파이썬 다익스트라(Dijkstra) 최단경로 문제 예

다익스트라 알고리즘

- 다익스트라는 최단경로를 구하는 알고리즘 중 가장 많이 사용되는 알고리즘 중 하나이다.

- 파이썬에서는 heapq를 활용하여  비교적 쉽게 구현할 수 있다. 

- 노드(vertex)와 간선(edges)으로 이루어진 그래프에서 단방향 혹은 양방향 최단 경로를 구할 때 사용한다.

- 간선은 음수를 가질 수 없다는 조건이 있어야 사용 가능하다. ( 간선의 가중치가 음수인 경우 사용 불가 )

- 특정 노드에서 다른 노드로 갈 때, 가능한 모든 경우의 간선으로 방문하여 노드 간 최소 거리를 찾는다.   

  → 한번 방문하여 노드 사이의 거리를 구했어도, 다른 더 짧은 경로가 있을 수 있으므로 검사한다. 

  → 노드로 들어오는 모든 경로를 탐색했다면, 그중 최소값을 두 노드간 거리로 선택한다. 

다익스트라 애니메이션 ( 출처 : 위키 )

 

예제

- 보통 알고리즘 문제에서는 아래 그림처럼 노드가 있고, 각 노드를 연결하는 간선과 그 간선의 가중치가 주어진다.

- 다음 두 가지 예제를 통해 파이썬으로 다익스트라 알고리즘을 구현하는 방법을 살펴보겠다.

  1) 5번노드에서 출발하여 모든 노드를 방문할 때, 모든 노드까지의 최단거리 구하기.(단방향)

  2) 5번노드에서 출발하여 모든 노드를 방문한 후 다시 5번 노드로 돌아오는 최단거리 구하기.(양방향)  

예제 1) 코드

- 위 그래프를 보면, 노드 5번에서 다른 노드로 바로 가는 것보다 다른 노드를 거쳐 가는 것이 최단 경로일 경우가 있다.

  ( 5 → 2 : 50, 5 → 3 → 2 : 45 )

- 그러므로 한번 방문한 노드라도 다른 노드로부터 왔다면, 다시 방문하여 거리를 비교해야하 한다. 

from heapq import heappush,heappop
def dijkstra(graph,start):
    q = list() ## heapq 생성을 위한 초기 list 
    distance = dict() ## dist 저장을위한 dict 

    distance[start] = 0 ## 시작 노드의 거리는 0
    heappush(q, (0, start)) ## 거리,노드 순으로 q에 넣어서 오름차순 정렬할 것.

    while q:
        dis, node = heappop(q) ## heapq의 값중 거리가 가장 작는 값 꺼내기

        ## 방문할 노드까지의 직접 거리가 현재 확보된 경유거리보다 크면 다음 loop로
        if node in distance and (distance[node] < dis):
            continue

        ## 다음 노드 까지의 거리가 없거나 현재 업데이트된 거리보다 작으면 업데이트
        for key, value in graph[node]:
            cost = distance[node] + value
            if (key not in distance) or ((key in distance) and (cost < distance[key])):
                distance[key] = cost
                heappush(q, (cost, key))
    return distance

graph = {
1 : [(4,15),(5,35)],
2 : [(3,30)],
3 : [(2,40),(5,20)],
4 : [(1,25),(5,10)],
5 : [(3,5),(4,30),(2,50)],
}
distance = dijkstra(graph, 5)
print(distance.values())
print(sum(distance.values()))

- python heapq 패키지를 통해 heappush,heappop 함수를 사용할 수 있다. 

  1) heappush : list를 우선순위큐(heap)으로 만들고 값을 집어넣음 

  2) heappush : heap에 들어있는 값을 작은 값부터 뽑음(오름차순 정렬)

- heap의 요소로 여러개의 값이 들어갈 경우 먼저 들어간(앞의 value) 값부터 오름차순 정렬 한다. 

 

예제 2) 코드

- 예제 1의 코드를 그대로 이용하여, 기존 graph를 역으로 전환하여 다익스트라 알고리즘을 적용한다. 

  ( 기존 graph의 start:end 노드를 반대로 바꿔준다. )

- 기존 정방향 distance와 역방향 distance를 더하면 5번 노드에서 출발하여 돌아오는 모든 거리의 합이 된다. 

from heapq import heappush,heappop
def dijkstra(graph,start):
    q = list() ## heapq 생성을 위한 초기 list
    distance = dict() ## dist 저장을위한 dict

    distance[start] = 0 ## 시작 노드의 거리는 0
    heappush(q, (0, start)) ## 거리,노드 순으로 q에 넣어서 오름차순 정렬할 것.

    while q:
        dis, node = heappop(q) ## heapq의 값중 거리가 가장 작는 값 꺼내기

        ## 방문할 노드까지의 직접 거리가 현재 확보된 경유거리보다 크면 다음 loop로
        if node in distance and (distance[node] < dis):
            continue

        ## 다음 노드 까지의 거리가 없거나 현재 업데이트된 거리보다 작으면 업데이트
        for key, value in graph[node]:
            cost = distance[node] + value
            if (key not in distance) or ((key in distance) and (cost < distance[key])):
                distance[key] = cost
                heappush(q, (cost, key))
    return distance

graph = {
1 : [(4,15),(5,35)],
2 : [(3,30)],
3 : [(2,40),(5,20)],
4 : [(1,25),(5,10)],
5 : [(3,5),(4,30),(2,50)],
}
distance = dijkstra(graph, 5)
print(distance.values())
print(sum(distance.values()))
from collections import defaultdict
## 기존 graph를 역으로 계산 ( 출발:도착 노드를 변경 )
reverse_grapph = defaultdict(list)
for key,value  in graph.items() :
    for v in value :
        reverse_grapph[v[0]].append((key,v[1]))
## 변경된 graph를 다익스트라 알고리즘으로 최단거리 계산
reverse_distance = dijkstra(reverse_grapph, 5)
print(reverse_distance.values())
print(sum(reverse_distance.values()))
print('total_cost : ', sum(reverse_distance.values())+sum(distance.values()))

- collections 패키지의 defaultdict 함수를 이용해 value가 list인 dictionary를 쉽게 만들 수 있다.