daniel00   3년 전

안녕하세요.

플로이드 와샬로 All pairs shortest path problem 을 풀때

정점의 수가 십만개정도를 넘어서도 구현이 가능한가요?

일단 2차원 배열을 사용하지 못할거 같고,  시간복잡도도 O(V^3)이라면 타임아웃이 될 것 같아서요.

플로이드 와샬 알고리즘으로 구현가능한 최대 정점의 수에 제한이 있는지 궁금합니다.


jh05013   3년 전

일단 구해야 되는 것부터 O(V^2)개나 되어서 정점이 10만개일 수는 없습니다.

daniel00   3년 전

답변 감사합니다.

어디선가 정점10만개, 간선10만개 일때 모든 정점에 이르는 최단거리를 구하는 문제를 접한적이 있어서요.

아마도 그 문제는 다익스트라+인접리스트로 풀어야 하는가보네요.

감사합니다.

jason9319   3년 전

트리라는 조건이 붙는다면 LCA를 이용해서 해결할 수도 있을거 같네요

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