다익스트라 알고리즘(Dijkstra’s algorithm) : 모든 정점까지의 최단 경로 구하기
다익스트라 알고리즘은, 그래프 내의 특정 정점에서 갈 수 있는 모든 정점들까지의 최단 경로를 구하는 알고리즘입니다.
다익스트라 알고리즘은 그 방식이 효율적이라 그래프가 큰 경우에도 사용 가능한 장점이 있습니다.
하지만, 그래프 내 간선의 가중치가 음수인 것이 하나라도 있다면 사용할 수가 없습니다.
다익스트라 알고리즘 : 과정 확인하기
1번 정점에서 시작해서 모든 정점들까지의 최단 경로를 구한다고 가정해 보겠습니다.
정점들 간의 간선의 가중치는 그림과 같고, distance 배열은 1번 정점에서 특정 정점까지의 최단 경로 길이를 표시해 놓습니다.
단, 초기에는 최단 경로를 구하지 않은 상태이므로 무한대(아주 큰 값)로 표시합니다.
1번 정점에서 인접한 정점들을 살펴봅니다.
처음에는 모두 무한대 값들이었으므로, 1번 — 특정 정점 까지의 간선 가중치로 모두 업데이트가 될 것입니다.
즉, distance[특정 정점] 과 distance[1] + (1번 정점과 특정 정점 사이 가중치) 를 비교해 더 작은 값으로 distance[특정 정점] 을 업데이트합니다.
이것이 다익스트라 알고리즘의 핵심 과정이자 전부라고 할 수 있습니다.
이제 5번 정점에서 인접 정점을 살펴봅니다. 1번은 이미 처리했으므로, 4번 정점과의 거리만 살펴봅니다.
distance[4] 값은 1에서 바로 4로 갈 때의 거리인 9 였는데, 5번 정점에서 살펴보니, 1번에서 5번을 거쳐(distance[5]), 4번으로 가는 경로(5와 4 사이 가중치) 가 더 짧음을 알 수 있습니다.
즉, distance[4] > distance[5] + 2 이므로, distance[4] 를 distance[5]+2 로 업데이트합니다.
다음 정점들에 대해서도 이제 마찬가지로 수행하면 됩니다.
다익스트라 구현하기
백준 1916번 - 최소비용 구하기 : https://chanhuiseok.github.io/posts/baek-15/