백준 [boj 1504 번: 특정한 최단 경로] - 다익스트라 시각화

 

이번 글에서는 코드가 돌아 가는 과정을 시각화함으로써 코드에 대한 이해도를 높여 보려고 한다.

 

백준 1504 특정한 최단 경로

1504번: 특정한 최단 경로

 

 

먼저 코드를 보자

 

int dickstra(int start, int destination) {
	//cout << "다익스트라 함수 시작점" << start << "\n";
	if (start == destination ) return 0;
	int res = 0;
	// 양방향 길임
	priority_queue< pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	pq.emplace(0, start); //cost, start
	dist[start] = 0; // 시작점 비용 
	
	while (!pq.empty()) {
		//cout << "while 진입" << "\n";
		int value = pq.top().first;
		int now = pq.top().second;
		pq.pop();
		if ( dist[now] < value) {
			
			continue;
		}
		// 만약 이미 갱신되어있는 코드가 큐에있는 값보다 이미 작으면
		// 해당 반복 건너뜀
		
		for (int i = 0; i < graph[now].size(); i++) {
			int nextVal = graph[now][i].first;
			int next = graph[now][i].second;

			// 두 정점 사이 간선이 여러개 존재 시 여기서 sort 또는 visit 제거
			// 이거 아님!! dist[next] = min(dist[next], dist[now] + nextVal );
			if (dist[next] > dist[now] + nextVal) { // 다음 정점으로 가는 간선 모두 확인한 후 큐에 넣는 것임
				dist[next] = dist[now] + nextVal;
				pq.push(pair<int, int>(dist[next], next)); // 무작정 삽입이 아니라 최소 경로인것이 확인 되면 삽입
				
			}
		
		

		}
	}
	res = dist[destination];

	if (res == 1e9) return -1;
	return dist[destination]; 
}

 

코드에서는 시작점의 비용을 0으로 업데이트 한 후 시작노드와 인접한 노드를 기준으로 차례로 방문하고, 거리가 갱신되면 갱신된 노드와 비용을 우선순위 큐에 삽입한다.

이 우선 순위 큐가 빌 때까지 while문을 반복한다.

 

 

 

 

예시 그래프

 

위의 그래프에서는 정점 6에는 도달 할 수없음으로 5번 정점까지의 distance를 구하는 과정을 따라가 보자.

다익스트라는 single sorce - all destination 을 기반으로 하고있기 때문에  정점 1번에서 부터의 각 정점으로의 최소 비용이 모두 dist[] 배열에 업데이트 된다.

 

먼저 start 는 항상 1번 정점이므로 dist[1] 을 0으로 설정 하고 나머지는 최소값과 비교하며 갱신하기 위해 제일 큰 값인 INF를 채워준다.

초기화

처음 for 문에서 정점 1번을 기준으로 인접한 정점을 방문하고 있다.

1번 정점과 인접한 정점은 각각 2,3,4 이므로 각각의 dist(비용)을 비교 하고 갱신 한다.

이때, 거리가 갱신 되면 우선 순위 큐에 비용과 함께 정점을 삽입한다.

거리가 업데이트 되면 우선순위 큐에

1번 노드 거리 갱신

1번 노드와 인접한 노드의 방문을 마치면 우선 순위 큐의 top에 있는 정점을 기준으로 거리를 갱신한다.

top에 있는 2번 노드를 pop하고 2번 노드의 인접한 노드를 방문 한다.

2번 노드의 경우 인접한 노드는 3번 뿐이다.

3번 노드의 비용은10+15(25)으로, 앞서 저장된 20보다 크기 때문에 우선 순위 큐에 들어가지 않는다.

dist[] 배열의 변화 또한 없다.

 

 

거리가 갱신되지 않아 새로 우선 순위 큐에 삽입 된 노드는 없다. 따라서 우선 순위 큐의 top에있는 3번 노드를 방문 한다.

4번 노드의 경우 41 보다 20+20(40) 이 크므로 거리가 갱신되고 4와 5는 우선 순위 큐에 삽입된다. priority_que는 앞에 있는 pair의 정수 기준으로 정렬 되므로 그림에서 처럼 4번 노드의 비용을 기준으로 오름차순 정렬된다.

 

3번 노드의 인접노드

3번 노드 인접 거리 갱신

4번 노드에서는 5번 노드의 거리가 갱신되고 우선 순위 큐에 삽입된다.

4번 인접노드 갱신

4번 인접노드 거리 갱신

pop!

다음으로 우선순위 큐에 있는 노드 4번이 다시 호출 되지만, 거리의 갱신은 되지않으므로 dist의 변화는 없다.

5번 또한 5번에서 다른 노드로 갈수 있는 간선이 없으므로 변화가 없다. 

 

 

 

5번 노드로의 최종적인 경로는 아래 그림과 같이 정점 1, 3, 4 ,5 거쳐 dist[5] = 60으로 마무리 된다.

최종 distance

최종 경로