joonas   2년 전

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

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

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

yukariko   2년 전

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

v의 max가 20000 이니까

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

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

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

joonas   2년 전

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

joonas   2년 전

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

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

다익스트라 쓰세요 ㅜㅜ 

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

___   2년 전

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

joonas   2년 전

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

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