파이썬 다익스트라 알고리즘 사용하기

다익스트라 알고리즘

 

다익스트라 알고리즘은 탐색 알고리즘으로 최단경로를 찾는 알고리즘이다. 이름이 다익스트라인 이유는 이 다익스트라 알고리즘을 만든 사람의 이름이 '에츠허르 데이크스트라'라서 라고한다.

 

이 알고리즘의 핵심은 가중치가 있는 그래프에서 비용(cost)가 가장 적은 경로를 찾는데에 있다.

다익스트라 알고리즘이 네비게이션 같은 GPS 소프트웨어 많이 활용된다.

 

초기의 다익스트라 알고리즘은 O(V^2)의 시간복잡도를 가졌었지만, 이후 우선순위 큐로 인한 개선으로 O((V+E)LogV)를 가지게 되었다.

 

 

과정

(그래프는 인접행렬이든 인접리스트이든 상관없다. 허나 글에선 편의를 위해 인접행렬 사용)

상황은 보라색 정점에서 주황색 정점까지 가야하는데 가장 적은 비용으로 가야한다.

(보라색 정점 = 0, 파란색 정점 = 1, 분홍색 정점 = 2, 주황색 정점 = 3)

 

• 보라색 정점에서 시작을 한다.
• 보라색 정점에서 보라색 정점으로 이동할 때 비용이 0이 드므로 dist[0]에 0을 할당.
• 보라색 정점에서 파란색 정점으로 이동할 때 비용이 4이므로 dist[1]에 4 할당
• 보라색 정점에서 분홍색 정점으로 이동할 때 비용이 1이므로 dist[2]에 1 할당
• 파란색 정점에서 주황색 정점으로 이동 할 때 비용이 2이므로 보라색에서 파란색까지의 비용 + 파란색 정점에서 주황색 정점으로 가는 비용 = 6, 6을 dist[3]에 할당해준다.
• 분홍색 정점에서 주황색 정점으로 이동할 때 비용이 8이므로 보라색에서 분홍색까지의 비용 + 분홍색 정점에서 보라색으로 가는 비용 = 9, 9를 dist[3]에 할당하기 전에 원래 값이 있었기 때문에, 원래 값보다 작은지 비교를 한다. 원래 값이 더 작기 때문에 dist[3]에 할당을 하지 않는다.

 

그러면 이러한 dist가 생긴다.

 

dist = [0,4,1,6]

 

이러면 보라색 정점에서 어디든 가는 최단거리를 알 수 있다.

 

코드로 요약

 

1. 일단 보라색에서 거리를 저장하는 dist 리스트(배열)를 만든다. 이때 dist는 INF로 채워준다.

   (INF는 인피니티로 무한을 뜻한다. 필자는 INF를 sys.maxsize로 매우 큰 값으로 할당해주었다.)

2. 큐를 하나 만들고, 큐에 시작비용과 시작정점을 넣어준다.(큐는 리스트,배열을 큐처럼 사용해도 무방, 시작비용은 당연히 0이고 시작정점 또한 0이다. 보라색 정점을 0이라 해줬기 때문.)

3. 이후 while문을 돌리면서 현재 정점에 연결되있는 정점까지 가는 비용과 그 연결된 정점을 큐에 넣어준다. (물론 방문했던 정점은 큐에 넣지 않는다.) 그리고 while문이 돌아갈때 마다 큐에 있는 것을 pop해주면서 dist를 완성해준다. 

 

 

import sys

n,m = map(int, sys.stdin.readline().split())

INF = sys.maxsize

dist = [INF for _ in range(n)]

graph = [[0 for _ in range(n)] for _ in range(n)]

for _ in range(m):
    a,b,c = map(int, sys.stdin.readline().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c

def dijkstra():
    queue = []
    queue.append([0,0])
    visited = []
    while queue:
        temp = queue[0]
        del queue[0]
        cost = temp[0]
        now = temp[1]
        if dist[now] > cost:
            dist[now] = cost
        visited.append(now)
        for i in range(n):
            if graph[now][i] != 0 and i not in visited:
                queue.append([cost+graph[now][i], i])

dijkstra()
print(dist)

n은 정점의 개수, m은 간선의 개수이다. 우선순위 큐를 사용하지 않은 코드인다. 우선순위 큐를 사용하려면, heapq로 바꿔주면 된다.