글 읽기 - 다익스트라에서 왜 visited를 사용하지 않아도 답이 나올까요?

kyy627 7년 전 0

visited를 체크해주면 오히려 틀렸습니다가 나옵니다.

아래 소스에서 왜 visited를 체크하지 않아도 정답이 나오는 건지,

visited를 추가하면 왜 오답이 나오는 건지 궁금합니다.

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
// 방향그래프, 시작점에서 다른 모든 정점의 최단 경로
// 간선의 가중치는 10이하의 자연수
// -> 다익스트라
const int MAX_VALUE = 0x7fffffff;
int V, E, K;
vector<pair<int, int> > edge[300001];
priority_queue<pair<int, int> > pq;
int dist[20001];
int main() {
	// INPUT
	scanf("%d %d", &V, &E);
	scanf("%d", &K);
	for (int i = 1; i <= E; i++) {
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		edge[u].push_back(make_pair(w, v));
	}

	// INIT
	for (int i = 1; i <= V; i++) {
		if (i == K)
			dist[i] = 0;
		else
			dist[i] = MAX_VALUE;
	}

	// CALCULATE
	pq.push(make_pair(-0, K));
	while (!pq.empty()) {
		int curNode = pq.top().second;
		int curCost = -pq.top().first;
		pq.pop();

		for (int i = 0; i < edge[curNode].size(); i++) {
			int nextNode = edge[curNode][i].second;
			int nextCost = edge[curNode][i].first;
			if (dist[nextNode]>curCost+nextCost) {
				dist[nextNode] = curCost + nextCost;
				pq.push(make_pair(-dist[nextNode], nextNode));
			}
		}
	}

	for (int i = 1; i <= V; i++) {
		if (dist[i] == MAX_VALUE)
			printf("INF\n");
		else
			printf("%d\n", dist[i]);
	}
	return 0;
}

sksdong1 7년 전 5

visit 체크를 하면 나중에 발견된 경로가 더 짧더라도 무시되겠죠

gallopsys 7년 전 7

간단하게 예를 들어드리는 게 빠르겠네요. 일단 해당 문제의 예제 테스트 케이스를 약간만 변형해봅시다.

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 1

이라는 그래프가 있다고 가정해봅시다. 일단 정점 1부터 시작한 그래프는 visited로 체크해가며 최단경로를 계산한다고 해봅시다.

정점 1에서 출발하면 다익스트라 알고리즘에 의해 정점 2, 3을 방문하여 최단거리를 갱신하게 되고 이는 각각 2, 3인 비용을 갖습니다. 그리고 우선순위 큐의 동작에 따라 방문 거리가 최소점인 정점을 방문하게 됩니다. 다음 방문 정점은 2가 되겠죠.

정점 2로 갔는데, 방문할 수 있는 노드가 3과 4지만, 3은 이미 visited처리 되었기 때문에 방문할 필요가 없습니다. (이는 어디까지나 visited를 넣어 처리한 결과임을 알려드립니다.) 4는 한번도 방문한 적이 없기 때문에 정점 2의 최소비용인 2와 정점 2에서 정점 4로 가기 위한 비용인 5를 더해 7로 갱신했습니다.

정점 5는 방문할 수 없기 때문에 무한대의 값을 가지게 되지만, visited로 체크한 결과, 더 이상 방문할 정점이 없기 때문에 탐색할 필요가 없습니다. 하지만 항상 옳은 결과를 내놓을까요?

아닙니다. 위에서 변형된 테스트 케이스로 보면 정점 1에서 출발하여 정점 3, 정점 4를 거치게 되면 3 + 1로 비용 4를 갖게 되므로 정점 1에서 출발하여 정점 2, 4를 거친 비용인 7보다 더 최단거리를 가짐을 알 수 있습니다.

그러므로 다익스트라 알고리즘에서 visited를 두면 이러한 경우를 체크하지 못하게 되고 논리적 오류가 발생할 수도 있는 것이지요.

ckdfuf2001 6년 전 1

값이 바뀐 경우에 visit 을 다시 false로 바꾸어야 합니다.

예를 들어

1-1: 10 (1에서 1가는데 10)

1-3: 2 (1에서 3가는데 2)

3-1: 2 (3에서 1가는데 2)

인 경우를 생각해 보시면 됩니다.

1은 1,3을 큐에 넣고 visit 해놓아 다음이 1인 경우에는 동작하지 않지만

3에 가서 1의 값이 바뀌엇을때에는 visit을 해제해주어야 합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

다익스트라에서 왜 visited를 사용하지 않아도 답이 나올까요?

kyy627 7년 전 0

sksdong1 7년 전 5

gallopsys 7년 전 7

ckdfuf2001 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말