BFS와 다익스트라 알고리즘을 통해 그래프에서 특정 노드까지의 최단 거리를 구할 수 있다.
BFS를 통해 계산하는 경우는 한 번 이동할 때 카운트를 하나씩 늘려가면 되고.. 해당 개념을 사용해 문제도 좀 풀어봐서 익숙하다. 이 때, 간선의 가중치는 1만 가능하다.
다익스트라 알고리즘은 간선의 가중치가 0이상 일 때 사용할 수 있다.
다익스트라 알고리즘에 대해 자세히 알아보자.
Dijkstra
그래프 자료구조와 시작 노드가 주어지고, 시작점에서 모든 노드까지의 최단 거리를 출력하는 알고리즘이다.
dist[] : 시작점에서 특정 정점까지의 최단 거리를 담는 배열이다. (다익스트라의 결과를 담는 배열)
D (v, d) : 시작점에서 v까지 가는데 d만큼이 사용된다.
1. 시작점을 S라고 하자. dist[i]에서 i == S이면 0, 그렇지 않으면 Integer.MAX_VALUE로 저장한다.
2. D에 (S, 0)을 추가한다.
3. D에 있는 (v, d)세트 중 d가 가장 작은 값을 뽑아오고, dist[v]값과 비교해 값을 갱신한다.
4. 연결된 간선이 있으면 다시 갱신해준다.
음수 간선이 있는 경우, 한 정점이 v로 추출되는 경우가 여러 번 발생해 경우에 따라 무한 루프를 돌 수도 있다.
그림을 그려 살펴보면 쉽게 이해할 수 있다..
시간복잡도 : O(E logE) = O(E log V)
관련 문제를 많이 풀어 익숙해지자.