nlkey2022   6년 전

1.  BFS를 사용해서 해당 end에 도달하지 못하면 gg

2. 음수 사이클에 end가 들어있으면 Gee

3. 나머지는 최단거리 출력


어떤 반례가 있을가요?

jh05013   6년 전

음수 사이클에 end가 들어 있을 필요는 없습니다.

nlkey2022   6년 전

자세하게 설명해주실수 있으신가요??

jh05013   6년 전

음수 사이클 밖에 end가 있어도 사이클에서 end로 갈 수 있으면 "Gee"라는 뜻이었는데, 실제 코드도 그렇게 나오네요...? "음수 사이클에서 end로 갈 수 있을 때 Gee"를 의도하신 것 맞나요?

nlkey2022   6년 전

@jh05013 

i = 4일때

4 0 3 4
0 1 1
1 2 1
2 0 1
0 3 1
2 2 2 0
4 -> 1
9 10 8 8
4 -> 2
9 10 11 8
4 -> 0
12 10 11 8
4 -> 3
12 10 11 11
Gee

이렇게 돌아갑니다 ㅠㅠ



nlkey2022   6년 전

의도한건 아닌거 같은데 

벨만포드가 정점-1 번 만큼 엣지의 dist[to] > dist[from] + cost를 물어보는 성질때문에

0 -> 1 -> 2 만 음수 사이클로 판단하는게 아니라

0 -> 1-> 2 -> 3으로 음수 사이클을 판단하네요....

nlkey2022   6년 전

검색하면서 반례를 찾긴 찾았습니다!!

3 0 2 4

0 1 9999

1 2 9999

1 1 9999

0 2 0

10000 10000 10000

Gee

출처: http://stack07142.tistory.com/273 [Hello World]

제 코드에서는 20000으로 출력하네요 ㅠㅠ


nlkey2022   6년 전

해결했습니다!!

http://stack07142.tistory.com/... 천천히 읽어보면서 공부했고..

3 0 2 4

0 1 9999

1 2 9999

1 1 9999

0 2 0

10000 10000 10000

Gee

같은 예제 에서 end까지 가는 두경로 (한개는 무한대, 한개는 유한한수) 가 있을때

무한히 증가하는 경로의 값을 LONG_MAX로 박아두면 다음 벨만포드 검사할때 

dist[to] < dist[from] + cost 이부분 을 검사할 필요가 없어지네요!!

이 문제 덕분에 벨만 포드와 그래프 문제에 대해 많은거 배우고 갑니다 ㅠㅠ 저는 아직 부족하네요

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