글 읽기 - 벨만포드 알고리즘 질문있습니다.

joonas 9년 전 0

1753 최단경로 문제는 벨만포드로는 풀 지 못하는건가요?

아니면 제가 소스를 잘못 작성했나본데 어디서 예외가 생기는건지 잡을 수가 없네요 도와주세요 ㅠㅠ

그래프에서 예외를 만드는 노하우라도 있나요 으어어

#include <iostream>
#include <memory.h>
using namespace std;

#define INF 987654321
#define MAX 20001

int*  graph[MAX];	// 방향 그래프
int* length[MAX];	// 최단 경로 길이

void BellmanFord(int,int);

int main()
{
	int i, v, e, w, sp = 0, tv, te;
	cin >> v >> e >> sp;

	for (i = 0; i < v; ++i){
		graph[i]  = new int[v + 1];
		length[i] = new int[v + 1];
		for (int j = 0; j <= v; ++j)
			graph[i][j] = INF, length[i][j] = 0;
	}

	for (i = 0; i < e; ++i){
		cin >> tv >> te >> w;
		graph[tv - 1][te - 1] = length[tv - 1][te - 1] = w;
	}

	BellmanFord(v, e);

	for (i = 0; i < v; ++i){
	//	cout << sp << "에서 " << i + 1 << "로 가는 최단 경로 : ";
		tv = sp - 1 == i ? 0 : length[sp - 1][i];
		if (tv < INF) cout << tv;
		else cout << "INF";
		cout << endl;
	}

	return 0;
}

void BellmanFord(int V, int E)
{
	int n, i, j, k;
	for (i = 0; i < V; ++i)
		for (j = 0; j < V; ++j)
			length[i][j] = graph[i][j];	// 초기 설정 이동량

	for (n = 0; n < V - 1; ++n)	// 아래 행동을 V-1만큼 반복한다.
    for (i = 0; i < V; ++i){	// 시작점
        for (j = 0; j < V; ++j){	// 경유점
            for (k = 0; k < V; ++k){	// 도착점
                if (i != k && length[i][j] + graph[j][k] < length[i][k])
                {
                    // 경유하는 길이 더 최단경로라면 경로를 갱신
                    length[i][k] = length[i][j] + graph[j][k];
                }
            }
        }
    }
}

yukariko 9년 전 0

graph,length 포인터 배열의 크기가 20000 이고

v의 max가 20000 이니까

위의 동적할당은 메모리는 총 20000*20000 * 4가 되서

메모리 초과가 발생해야 정상인데

그것과 관련있는건 아닐까?

joonas 9년 전 0

이거 잘못짠거같다. 벨만포드는 O(VE) 여야하는데 이거 O(V^4)네 ㅎㄷㄷ. 다시 짜야지... ㅠㅠ

joonas 9년 전 0

해결했는데 자문자답 남길게요.

결론부터 말하면 벨만-포드 알고리즘은 시간초과가 나옵니다. O(VE) 인데 VE가 10^9을 넘거든요.. ㅠㅠ

다익스트라 쓰세요 ㅜㅜ

그리고 제가 게시글로 적은 소스는 "뻴만포드"보단 "플로이드" 알고리즘이 맞는거같네요.. 여튼 둘다 실패 (...)

___ 9년 전 0

벨만포드로 제출해봤는데 맞은걸 보니 ...최악의 경우까지는 발생하지 않고 이런 저런 케이스만 많은것 같네요.

joonas 9년 전 0

네. 벨만포드로 2번 제출했는데 2번째는 정답 받았네요ㅎㅎ VE를 ElogV 로 줄이니 되더군요.

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

문제

문제

출처

ICPC

벨만포드 알고리즘 질문있습니다.

joonas 9년 전 0

yukariko 9년 전 0

joonas 9년 전 0

joonas 9년 전 0

___ 9년 전 0

joonas 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말