글 읽기 - 다익스트라 알고리즘 관련 질문...

bright2013 7년 전 0

위키 보고 작성한 다익스트라 알고리즘입니다.

STL 의 priority_queue 를 이용해 min_heap 만들었고,

다른 문제가 될만한 부분이 보이질 않네요. 예제 코드도 통과하는데

틀린 케이스를 못 찾겠습니다.

노드 수가 2만개에 에지 weight 도 10을 넘지를 않으니 인트 범위 넘어가서 그런 것도 아닌데..

도와주세요 ㅠㅠ

#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <tuple>
#include <set>
#include <queue>


using namespace std;

#define pii pair<int, int>
#define Graph vector<vector<pii>> 

#define F first
#define S second
#define undefined -1
#define INF 99999999

int V,E;
int start_v;

Graph adj_list;
vector<int> dist;
vector<int> prev_node;

void input(std::istream& pin) {
	pin >> V >> E;
	pin >> start_v;

	adj_list.resize(V);
	int r,c,cost;
	
	for(int i=0; i<E; i++) {
		scanf("%d %d %d", &r, &c, &cost);
		
		adj_list[r-1].push_back(make_pair(c-1, cost));	
	}	
}

void get_shortest_path_by_dijkstra(Graph& graph, int& source) {
	int u;
	priority_queue<pii, vector<pii>, greater<pii>> pri_Q;
	
	// set source distance to 0
	dist[source] = 0;

	for(int i=0; i<V; i++) 
		pri_Q.push(make_pair(dist[i], i));
	
	while(!pri_Q.empty()) {
		//pick the top element
		u = pri_Q.top().S;
		pri_Q.pop();

		for(auto& it : graph[u]) {
            int alt = dist[u] + it.S;
			if(alt < dist[it.F]) {
				dist[it.F] = alt;
				prev_node[it.F] = u;
			}	
		}
	}	

}

int main() {
	
	input(cin);

	dist.assign(V, INF);
	prev_node.assign(V, undefined);

	start_v--;
	get_shortest_path_by_dijkstra(adj_list, start_v);
	
	for(auto& it : dist) {
		if( it >= INF) printf("INF\n");
		else 
			printf("%d\n", it);	
	}

	return 0;
}

yukariko 7년 전 0

다익스트라 구현이 잘못되었습니다.

일단 prev_node는 필요없어 보입니다.

그리고 다익스트라는 dist값이 작은 순으로 추출되어야 하는데,

위 코드는 source를 제외한 나머지 모든 정점이 INF로 동일해서

dist의 변경이 반영되지 않습니다.

참고로 위키의 pseudo 코드는 pq를 사용하는 경우에는 적합하지 않습니다.

bright2013 7년 전 0

감사합니다~~^^

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

문제

문제

출처

ICPC

다익스트라 알고리즘 관련 질문...

bright2013 7년 전 0

yukariko 7년 전 0

bright2013 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말