[백준][BOJ1753] 최단경로

Algorithm/Dijkstra

by bedamino 2021. 7. 7. 22:22

1. 문제 : https://www.acmicpc.net/problem/1753

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.

www.acmicpc.net

2. 풀이 : Dijkstra

3. 시간복잡도 : O(ElogV)

4. 설명

그림[1]의 그래프에서 시작점이 1번 노드 일 때, 각 노드까지의 최단거리를 구하는 방법은 다음과 같다.

시작점인 1번 노드를 우선순위큐에 삽입한다. 시작점에서 시작점까지의 최단거리는 0이다.

노드 1에서 최단 거리로 방문 할 수 있는 노드를 우선순위큐에 삽입하고, 최단 거리를 갱신한다.

노드 2에서 최단 거리로 방문 할 수 있는 노드를 우선순위큐에 삽입하고, 최단 거리를 갱신한다.

노드 3에서 최단 거리로 방문 할 수 있는 노드를 우선순위큐에 삽입하고, 최단 거리를 갱신한다.

노드 5에서 최단 거리로 방문 할 수 있는 노드를 우선순위큐에 삽입하고, 최단 거리를 갱신한다.

노드 4에서 최단 거리로 방문 할 수 있는 노드를 우선순위큐에 삽입하고, 최단 거리를 갱신한다.

노드 8에서 최단 거리로 방문 할 수 있는 노드를 우선순위큐에 삽입하고, 최단 거리를 갱신한다.

우선순위큐에 남아있는 나머지 노드 정보는 최단 거리에 영향을 주지 않으므로, 1번 노드에서 각 노드까지의 최단 거리는 그림[8]과 같다.

5. 코드

저작자표시 비영리 변경금지

날마다 새로운 코딩