다익스트라란?
1959년 다익스트라가 고안해낸 알고리즘인 다익스트라는 출발점으로부터 다른 각 마디로 가는 최단 경로가 존재하고, 이를 탐색할 때 사용하는 알고리즘입니다.
최단경로를 구하는 알고리즘이지만, BFS와 다른 점은 각 노드에 가중치가 있을 때 사용한다는 점이 다릅니다.
다만 다익스트라 알고리즘의 특징 중 하나는 음의 가중치를 가지는 간선이 없을 때 사용이 가능한 알고리즘이라는 것입니다.
다익스트라 알고리즘의 구현은 최소 힙이나 우선순위 큐를 사용하여 구현할 수 있습니다.
다익스트라의 시간 복잡도는 다음과 같습니다. O(ElogV) 여기서 V는 노드 수이며, E는 에지(간선)의 수입니다.
다익스트라 알고리즘의 탐색 과정
먼저, 주어진 그래프를 인접리스트로 변환합니다.
다음은 최단거리 배열을 초기화해줍니다.
주어진 노드의 개수만큼 배열을 선언합니다.
출발노드인 A의 값은 0으로 초기화하고, 나머지는 무한대값(모든 Edge의 가중치보다 큰 값)으로 설정해서, 최단거리를 비교할 수 있도록 해줍니다.
노드에 대한 최단거리 배열의 갱신은 위와 같이 이루어집니다.
A에서 B로 갈 때, 즉. graph[A]의 최단거리 값 + graph[B]의 최단거리 값이, 기존의 최단거리 값보다 작다면, (초기값은 무한이기 때문에 무조건 true)
값을 갱신해줍니다.
이러한 과정을 모든 노드의 에지를 탐색할 때까지 반복합니다.
위 그림에 따르면, D정점의 경우. 최초 12로 갱신되었다가, graph[B]+1의 값이 12보다 작기 때문에, 11로 갱신되었음을 확인할 수 있습니다.
마지막 간선인 D->E를 체크하여, 최단거리를 체크합니다.
최종적으로 A에서 E로 가는 최단 거리는 14가 되며, 최단거리 배열의 E 인덱스에 저장된 값을 반환함으로써 얻을 수 있습니다.
코드 구현
백준에서 제공하는 '간선 이어가기 2' 문제입니다.
다익스트라 알고리즘을 이용하여 해결할 수 있습니다.
특정 정점, S와 T가 연결되는 시점의 가중치 합이 최소가 되도록, 연결하고 그 값을 구하는 문제입니다.
즉, S가 start 지점이 되며, T가 end 지점입니다.
앞서 설명했다시피,
최단거리 배열을 INF값(모든 가중치를 더해도 남을 아주 큰 값)으로 초기화해줍니다.
이후, 그래프의 가중치와 노드를 저장하기 위해서 이중벡터를 선언 후, pair 형태로 모든 간선의 데이터를 초기화해줍니다.
다익스트라 알고리즘은, 우선순위 큐를 이용하여 구현할 수 있습니다.
큐에, 시작 지점의 데이터.
즉, S 노드와 가중치 0을 넣고 탐색을 시작합니다.
탐색은 while문을 이용하는데, 큐에 원소가 더이상 존재하지 않을 때까지 반복합니다.
현재 큐의 top()에 저장된 노드(pair.second)와 가중치(pair.first)를 저장 후, pop()하여 큐에서 현재 간선을 제외합니다.
만약 currentNode가 목표(t)와 일치할 경우에, 곧장 current 노드를 인덱스로 갖는 가중치 값을 반환함으로써 탐색을 마칩니다.
그렇지 않다면, 그래프에 저장되어 있는 현재 노드와 이어진 인접한 모든 간선을 큐에 저장하면서 최단거리 배열의 값을 갱신해줍니다.
위에서 설명한 것과 마찬가지로
최단거리 배열[현재노드] + 인접한 다음 노드의 가중치 < 최단거리 배열[인접한 다음 노드]를 만족했을 때.
최단거리 배열[인접한 다음 노드] = 최단거리 배열[현재 노드] + 인접한 다음 노드의 가중치 로 최단거리를 수정하고, 큐에 해당 노드와 가중치를 Push 해줘서, 새로운 간선을 탐색할 수 있도록 해줍니다.
