안녕하세요.
플로이드 와샬로 All pairs shortest path problem 을 풀때
정점의 수가 십만개정도를 넘어서도 구현이 가능한가요?
일단 2차원 배열을 사용하지 못할거 같고, 시간복잡도도 O(V^3)이라면 타임아웃이 될 것 같아서요.
플로이드 와샬 알고리즘으로 구현가능한 최대 정점의 수에 제한이 있는지 궁금합니다.
답변 감사합니다.
어디선가 정점10만개, 간선10만개 일때 모든 정점에 이르는 최단거리를 구하는 문제를 접한적이 있어서요.
아마도 그 문제는 다익스트라+인접리스트로 풀어야 하는가보네요.
감사합니다.
트리라는 조건이 붙는다면 LCA를 이용해서 해결할 수도 있을거 같네요
댓글을 작성하려면 로그인해야 합니다.
daniel00 6년 전
안녕하세요.
플로이드 와샬로 All pairs shortest path problem 을 풀때
정점의 수가 십만개정도를 넘어서도 구현이 가능한가요?
일단 2차원 배열을 사용하지 못할거 같고, 시간복잡도도 O(V^3)이라면 타임아웃이 될 것 같아서요.
플로이드 와샬 알고리즘으로 구현가능한 최대 정점의 수에 제한이 있는지 궁금합니다.