[대표 유형] 다익스트라 알고리즘

문제 설명

정점의 개수 n과 단방향 간선 정보가 담긴 edges가 매개 변수로 주어질 때 1 번 정점에서 출발하여 n 번 정점에 도착하기까지 최단 경로의 길이를 반환하는 solution 함수를 작성하시오.

개념 설명

다익스트라 알고리즘(Dijkstra Algorithm)은 임의의 그래프가 주어졌을 때 고정된 한 정점에서 다른 정점들까지의 최단 경로를 구하는 알고리즘입니다.
다익스트라 알고리즘을 적용하기 위해서는 그래프에 주어진 간선의 가중치(경로의 비용)가 모두 양수이어야 하고 시간 복잡도는 $O(E log_2 V)$ 입니다.

다익스트라 알고리즘의 작동 방식은 다음과 같습니다. 먼저 다음과 같은 단방향 그래프가 주어졌다고 가정합니다.

이때 1번 정점에서 다른 정점들까지의 최단 경로 거리를 Dist[]로 두어 계산합니다. 초기에는 1번 정점을 제외한 모든 정점까지의 거리를 INF로 초기화합니다.

다음으로 1번 정점에서 시작하는 간선들을 바탕으로 다른 정점들의 최단 경로 Dist를 갱신합니다.

이후 방문하지 않은 정점(2, 3, 4, 5번 정점) 중 Dist가 최소인 정점을 방문하여 동일한 과정을 반복합니다. 현재 예시의 경우에는 3번 정점을 방문하고 간선 정보로 Dist를 갱신합니다.

다시 방문하지 않은 정점(2, 4, 5번 정점) 중 Dist가 가장 작은 2번 정점에 방문하여 Dist를 갱신합니다.

이러한 과정을 반복하여 모든 정점을 방문, Dist를 갱신하면 알고리즘을 종료합니다. 이를 우선순위 큐를 활용해 알고리즘을 구현한다면 시간복잡도는 $O(E log_2 V)$ 입니다.

제한 사항

• 정점의 개수n은 2 이상 10,000 이하의 자연수입니다.
• 단방향 간선 정보 edges는 최소 1개 최대 2,000,000개의 간선 정보를 갖고 있습니다.
• edges의 원소는 특정 간선의 시작 정점 x, 도착 정점 y, 간선의 길이 w로 이루어집니다.
  • x, y는 1 이상 n 이하의 자연수입니다.
  • w는 1 이상 10,000 이하의 자연수입니다.
• 1 번 정점에서 n 번 정점으로 가는 경로가 반드시 존재하도록 간선 정보가 주어집니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

앞선 예시의 설명과 같이 1번 정점에서 5번 정점까지의 최단 경로는 $1 \rightarrow 3 \rightarrow 5$이고 그 길이는 3입니다.

2번 테스트케이스 설명

1번 정점에서 9번 정점까지의 최단 경로는 $1 \rightarrow 2 \rightarrow 3 \rightarrow 5 \rightarrow 8$이고 그 길이는 16입니다.