biblus   2년 전

안녕하세요

해당 문제를 플로이드 알고리즘으로 구현했는데 python3는 시간초과가 떠서 pypy3로 제출했습니다.

그리고 python3로 맞춘 사람이 있나 궁금해서 찾아봤더니 다익스트라로 푸셨더라고요.

제가 생각에는 다익스트라를 V번 수행하는 것보다는 플로이드가 시간복잡도 상으로 낫다고 봤는데,

왜 다익스트라를 V번 수행하는게 더 빠른지 궁금합니다.

희소그래프에서는 다익스트라가 유리하다는 것은 이해가 됩니다.

그런데 밀집 그래프에서는 어떠한 알고리즘 원리 때문에 이렇게 되는지 알려주시면 감사하겠습니다.

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