[일반] 플로이드 워셜 질문

[익명(tlazhddl)]

다익스트라가 (V+E)logV고

플로이드 워셜이 V^3인데

음의 간선 없고 모든 노드쌍에 대해 최단거리 구해야될경우

다익스트라 x V번 하는게 플로이드 워샬보다 이득임?

[EN_SA(encludingsalt)]

E가 커져서 V²에 가까워질수록 플로이드 워셜이 이득이지만 실제 문제에서 logV 붙었다고 죽이는 문제는 잘 못본거 같은

[익명(tlazhddl)]

ㄷ

[익명(118.235)]

그래서 문제조건을 잘봐야댐 그래프가 얼마나 dense 한지 보고..

[익명(tlazhddl)]

ㅇㅎ

[아마게(aagzuegq2lmc)]

조건이 플로이드워셜만 허락하는 문제는 못본듯? 그냥 간편해서 쓰는거지 E때문에 터지는경우 못봄 - dc App

[익명(121.153)]

근데 일반적으로 플로이드워셜이 빠르긴한 듯?, 힙 썻다 지웟다도 없고, 메모리도 순차적으로 쭉 방문하니까