[파이썬/python] 다익스트라 알고리즘 (Dijkstra Algorithm)

다익스트라 알고리즘은 그래프에서 정점 간의 최단 경로를 찾는 알고리즘이다.

 

그래프에서 주어진 시작 노드에 대해서 다른 정점 간의 가장 짧은 경로를 찾는다.

즉, u에서 v로 갈 때 경로 중 간선들의 가중치 합이 최소가 되는 경로를 찾는 것이다.

이 알고리즘은 어떤 한 정점에서 다른 정점까지 가는 경로를 찾을 때

가장 짧은 경로가 결정되면 멈추는 식으로 사용한다.

 

파이썬으로 구현하기

위와 같은 그래프이고 시작노드가 1일 때, 

시작노드 : [(도착노드, 가중치)] 형식으로 딕셔너리를 만들면 아래와 같다

n = 1
graph = { 1: [(2,2), (3,3)],
          2: [(3,4), (4,5)],
          3: [(4,6)],
          5: [(1,1)]
        }

 

각 정점에 대한 시작노드부터 해당 정점까지의 가중치 합을 저장할 point 리스트를 만든다.

해당 리스트의 초기값은 무한한 값으로 1e9를 넣어주었다.

INF = int(1e9)
point = [INF]*(5+1)	# 모든 정점과 같은 인덱스가 있도록 정점개수 + 1 만큼 만듦

 

point를 표로 그려보면 아래와 같다.

인덱스 번호와 정점 번호가 같게 하기 위해 한칸 더 큰 리스트를 만들고 인덱스 0은 사용하지않는다.

정점 (인덱스)	0	1	2	3	4	5
point	INF	INF	INF	INF	INF	INF

 

dijkstra 알고리즘은 heapq를 사용하여 아래와 같이 구현하였다.

import heapq

def dijkstra(n):
    queue = []
    point[n] = 0
    heapq.heappush(queue, (0, n))

    while queue:
        c, now = heapq.heappop(queue) 
        
        if point[now] < c:  
            continue

        for node in graph[now]:
            cost = c + node[1]

            if cost < point[node[0]]:
                point[node[0]] = cost
                heapq.heappush(queue, (cost, node[0]))

 

queue는 탐색할 노드들의 (가중치 합, 정점) 쌍이 들어갈 리스트이다.

n은 시작노드로써 가중치 합인 point[n]을 0으로 초기화한다.

heapq를 이용하여 queue에 첫번쨰로 탐색할 노드에 n에 대한 (가중치 합, 정점)인 (0,n)을 넣는다.

 

queue에 탐색할 노드가 있는동안 반복된다.

heapq를 이용하여 queue에 있는 값을 꺼내 c, now에 넣는다.

c에는 이전 노드까지의 가중치 합이, now에는 현재 노드가 저장되어 있다.

 

만약 현재 노드까지의 가중치 합 point[now]가 이전 노드까지의 가중치 합 c 보다 작다면

c에서 now로 가는 가중치 합을 더해볼 필요없이 어차피 point[now]가 작으므로 아래 내용을 실행하지않는다.

 

만약 point[now]가 c보다 크다면 now에서 연결되는 정점들을 graph[now]를 통해 살펴본다.

node[0]에는 연결되는 정점의 번호가, now[1]에는 해당 정점으로 가는데의 가중치가 들어있을 것이다.

cost에 이전 노드까지의 가중치 합 + node[0]으로 가는데의 가중치를 더해 저장한다.

 

만약 cost가 원래 들어있던 cost[0]에 대한 가중치 합인 point[node[0]]보다 작다면

point[node[0]]를 cost로 갱신해주고 

다음을 탐색하기 위해 heapq를 이용하여 queue에 cost와 node[0]을 저장해준다.

 

---

위의 글로 된 설명이 이해가 안된다면 아래의 예시를 살펴본다.

 

우선 시작 노드 1에 대한 point 값을 0으로 바꿔주고 시작한다.

queue에는 1까지의 가중치 합 0, 정점 1을 저장한다.

정점 (인덱스)	0	1	2	3	4	5
point	INF	0	INF	INF	INF	INF

 

---

queue에 들어있는 값 (0,1)을 확인한다.

point[1]이 0으로 코드상 c와 같으므로 for문을 실행할 것이다.

 

graph[now]를 통해 1과 연결된 정점 2=(2,2)와 3=(3,3)을 탐색한다.

 

(2,2)의 경우,

이전 노드 1까지 가는데에 대한 가중치가 0이므로 2까지의 가중치 합 cost는 그대로 2가 된다.

cost=2는 기존에 들어있던 point[2]의 값 INF보다 작으므로 point를 갱신한다.

정점 (인덱스)	0	1	2	3	4	5
point	INF	0	2	INF	INF	INF

그리고 queue에 2까지의 cost 2와 정점 2를 저장한다. = (2,2)

 

(3,3)의 경우,

마찬가지로 이전 노드 1까지 가는데에 대한 가중치가 0이므로 3까지의 가중치 합 cost는 3이 된다.

cost=3은 기존에 들어있던 point[3]의 값 INF보다 작으므로 point를 갱신한다.

정점 (인덱스)	0	1	2	3	4	5
point	INF	0	2	3	INF	INF

그리고 queue에 3까지의 cost 3과 정점 3을 저장한다. = (3,3)

---

queue에 들어있는 다음 값 (2,2)를 확인한다.

point[2]가 2로 코드상 c인 2와 같으므로 for문을 실행할 것이다.

 

graph[now]를 통해 2와 연결된 정점 3=(3,4)와 4=(4,5)를 탐색한다.

 

(3,4)의 경우,

이전 노드 2까지 가는데에 대한 가중치가 2이므로 3까지의 가중치 합 cost는 6이 된다.

cost=6은 기존에 들어있던 point[3]의 값 3보다 크므로 point를 갱신하지 않는다.

 

(4,5)의 경우

이전 노드 2까지 가는데에 대한 가중치가 2이므로 4까지의 가중치의 합 cost는 7이 된다.

cost=7은 기존에 들어있던 point[4]의 값 INF보다 작으므로 point를 갱신한다.

정점 (인덱스)	0	1	2	3	4	5
point	INF	0	2	3	7	INF

그리고 queue에 4까지의 cost 7과 정점 4를 저장한다. = (7,4)

---

queue에 들어있는 다음 값 (3,3)을 확인한다.

point[3]이 3으로 코드상 c인 3과 같으므로 for문을 실행할 것이다.

 

graph[now]를 통해 3과 연결된 정점 4=(4,6)을 탐색한다.

 

(4,6)의 경우,

이전 노드 3까지 가는데에 대한 가중치가 3이므로 4까지의 가중치 합 cost는 9가 된다.

cost=9는 기존에 들어있던 point[4]의 값 7보다 크므로 point를 갱신하지 않는다.

---

queue에 들어있는 다음 값 (7,4)를 확인한다.

point[4]가 7으로 코드상 c인 7과 같으므로 for문을 실행할 것이다.

 

graph[now]를 통해 4와 연결된 정점을 확인해야하지만 연결된 정점이 없으므로 for문은 실행되지않는다.

---

이로써 queue에는 값이 없으므로 반복문을 종료한다.

최종 정점 간의 최단 경로 point는 다음과 같다.

정점 (인덱스)	0	1	2	3	4	5
point	INF	0	2	3	7	INF