dreamian   1년 전

SPFA는 벨만포드를 개선시킨 알고리즘이라고 학습하고 두 가지 방식으로 구현해보았는데,

벨만포드의 경우 4ms AC를 받았고 SPFA의 경우 8ms AC를 받았습니다.

분명 제가 구현한 SPFA 로직에 문제가 있을 것 같은데.. 어떤 부분인지 찾지 못하겠습니다.


SPFA의 경우

혹시, negative cycle을 더 빨리 찾는 로직을 넣어주면 되려나 해서 우선 순위큐로도 구현해보았는데 똑같이 8ms를 받았습니다.

또한, queue에 중복되는 원소가 들어가는지에 대해 디버깅해서 확인해보았는데 queue에 중복원소 삽입은 없었습니다.


어떤 경우가 문제가 되는 걸까요? ㅠㅠ

snrnsidy   1년 전

명쾌한 대답은 드리지 못하겠지만 아무래도 인간의 입장에서는 SPFA가 벨만 포드보다 간단할지 몰라도 컴퓨터 입장에서는 SPFA 함수에서의 IF문등 여러 가지 때문에 벨만포드보다는 더 느리지 않나 생각합니다. 

dreamian   1년 전

답변 정말 감사합니다!
어떤 알고리즘을 선택할 지는 신중해야겠군요 ㅠㅠ

ho94949   1년 전

SPFA는 음수 사이클이 없는 그래프에서 최단거리를 찾기 용이합니다. 음수 사이클이 있는 경우에는 벨만포드와 같고 + 더 느릴 수 있습니다.

Green55   1년 전

일단 SPFA도 평균 시간복잡도가 O(E)로 벨만포드와 같은거지, 최악의 시간복잡도는 O(VE)로 벨만포드와 같습니다.
따라서 랜덤데이터만 들어가있으면 보통 벨만 포드보다 훨신 빠르지만, 저격하는 데이터가 하나라도 들어가있으면 결국 벨만포드랑 다를게 없습니다.
4ms는 차이가 있다고 보기에는 너무 짧은 시간이라 그냥 이 문제에선 둘의 성능이 거의 같다라고 보셔도 무방할거 같습니다.
결국 그냥 편한거 쓰셔도 됩니다. 저는 그냥 무조건 SPFA만 씁니다.

dreamian   1년 전

두 분 모두 답변 정말 감사합니다. 배우는 입장에서 막연했었는데 도움이 많이 되었습니다!


@ho94949

SPFA가 음수 사이클이 있는 경우에는 벨만 포드보다 느리다고 하셨는데, 구현 상 부수적인 조건문들이 추가되어 그런건가요?

ho94949   1년 전

일단 벨만포드는 연산들이 간단한 편이니까요, 큐연산등등이 느릴 수 있을거에요

dreamian   1년 전

사소한 부분에도 답변달아주셔서  정말 감사합니다!

nhouyng   11달 전

어후 지저분해

ho94949   11달 전

@nhouyng ㅎㅇ

dreamian   11달 전

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