다익스트라 알고리즘
-
그래프에서 출발점부터 목적지까지의 최단 경로를 찾는 알고리즘 중 하나
-
각 간선의 가중치가 음수가 아닌 경우에 사용(이 경우엔 벨만-포드와 같은 다른 알고리즘 사용)
-
다익스트라 알고리즘은 다음 절차를 통해 구현
출발점에서부터의 최단 경로를 저장할 배열 (혹은 우선순위 큐)를 초기화. 출발점은 0으로, 나머지는 무한대로 초기화한다.
출발점에서부터 인접한 노드들을 탐색하면서, 현재까지의 최단 경로를 갱신한다. 각 노드의 최단 경로는 현재까지의 최단 경로와 해당 노드로의 가중치를 더한 값이다.
최단 경로가 갱신된 노드들 중에서 방문하지 않은 노드 중 가장 최단 경로가 작은 노드를 선택하고, 방문. 해당 노드와 인접한 노드들의 최단 경로를 갱신한다.
목적지 노드가 선택된 경우, 최단 경로를 찾은 것이므로 알고리즘을 종료. 그렇지 않은 경우, 3-4단계를 반복한다.
최적화?
위의 통상적인 다익스트라 알고리즘은 모든 노드를 방문하며, 인접한 노드들의 최단거리를 갱신한 후, 방문한 노드의 간선 중 가중치가 가장 낮은 간선을 통해 다음 노드로 이동하고 반복하며 진행된다.
이 때, 노드를 방문하는 기준을 '최단거리 갱신이 이루어진 노드'로 한정한다면 시간 효율을 개선할 수 있다. 어떻게 가능한 것일까?
예를 들어, 노드 A에서 B로 이동하는 경로가 갱신되지 않았다는 것은, A -> B를 거쳐 이동하는 경로의 다른 거리들도 갱신될 필요가 없다는 뜻이다. 기존의 다른 노드에서 B로 이동하는 더 짧은 경로가 있다는 뜻이니까. 이런 식으로 설계한다면 불필요한 노드 방문 횟수를 줄일수 있고, 프로그램의 효율 또한 증가시킬 수 있을 것이다.
- 예시)
import heapq
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
inputs = [list(map(int, input().split()))for _ in range(M)]
start, end = list(map(int, input().split()))
buses = [[]for _ in range(N+1)]
for bus in inputs:
heapq.heappush(buses[bus[0]],((bus[2], bus[1])))
visitList = []
costs = [float('inf')]*(N+1)
costs[start] = 0
heapq.heappush(visitList, (costs[start], start))
while visitList:
cost, position = heapq.heappop(visitList)
for bus in buses[position]:
if costs[bus[1]] > cost + bus[0]:
costs[bus[1]] = cost + bus[0]
heapq.heappush(visitList, (costs[bus[1]], bus[1]))
print(costs)- 백준 1916번: 최소비용 구하기
방문할 노드들과 해당 노드의 갱신된 cost를 우선순위 큐인 visitList에 담아 관리한다. 반복 전 출발 노드를 제외한 노드들의 cost들을 inf로 초기화해놓았기에 최소한 한번씩은 갱신이 된다. 여기서 추가로 우선순위 큐에 담긴 명령들을 처리할 때, 현재 해당 노드의 최단 경로보다 큰 비용을 가지고 방문하려 한다면 continue 시켜버리는 식으로 더욱 더 효율적인 처리를 할 수도 있겠다. 이유는 당연하게도 이미 더 짧은 거리를 찾은 노드에 방문할 필요는 없으니까 😄
- ex)
if cost > costs[position]:
continue이런 코드를 우선순위 큐에서 pop해온 직후 삽입해주는 식으로 말이야👍
