사용자 도구

사이트 도구


ps:전체쌍_최단_경로

전체쌍 최단 경로 (All-pairs shortest path)

  • 기본적으로는 거의 플로이드-와샬 알고리즘만 사용된다.
    • 만약 그래프가 Sparse 하다면 이론적으로는 다익스트라 알고리즘을 모든 노드에 대해서 돌리는 것이 더 효율적이다. 다익스트라 알고리즘을 피보나치 힙으로 구현했다면 O(|E||V|+|V|^2log|V|)이니까.. Dense 그래프에서도 O(|V|^3)보다 같거나 작다. 그러나 일반적인 바이너리 힙을 이용한 구현에서는 O(|E||V|log|V|)이다. |E|<|V|^2/log|V| 인 경우에만 더 값이 작다. 다익스트라의 상수항이 더 크다는 점을 고려하면 그래프가 꽤나 sparse 해야지 이 방법이 더 효율적일 것 같으니, 아예 |E|=O(|V|)인 경우 정도에나 한번 시도해 봐야겠다.

플로이드-와샬 알고리즘

  • 위키 에 의하면 빠른 행렬곱 연산을 이용해서 속도를 높이는 방법이 있다고 한다. 그렇지만 상수항이 커서 아주 큰 그래프에서만 효과있다고 한다. 아마도 PS에서는 신경안써도 될거 같다

구현상 고려

  • 인접행렬 형태로 주어진 그래프에서 O(|V|^3)에 계산된다
  • 입력값으로부터 그래프를 읽을때 인접행렬 형태로 읽어들이면 바로 수행할 수 있지만, 인접리스트 형태를 사용하는 다른 그래프 알고리즘과 일관성이 안맞는 문제가 있다.
  • 결국 인접리스트 형태의 그래프를 입력으로 받도록 만들었다. 함수 내부에서 인접행렬 형태로 그래프를 변환한 후 그걸 기반으로 최단경로를 계산해서 테이블을 돌려준다
  • path reconstruction이 필요할 경우도 있는데.. 지금은 고려 안함. 필요하면 나중에 생각해보겠음..

코드

관련 문제

토론

댓글을 입력하세요:
A X Z I M
 
ps/전체쌍_최단_경로.txt · 마지막으로 수정됨: 2021/01/27 11:45 저자 teferi