기본 콘텐츠로 건너뛰기

Floyd-Warshall Algorithm과 running time

정의
  • 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘
  • 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 
  • 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다.
running time
  • 플로이드-워셜 알고리즘으로 모든 정점 간 경로의 최소비용을 구하는 것은 O(V^3)의 시간 복잡도를 갖는다. 
  • 경유지를 기록한 경우, 경로를 역으로 추출하는 알고리즘의 복잡도는 O(V)의 시간 복잡도를 갖는다.
  •  종종 데이크스트라 알고리즘과 자주 비교되곤 하는데, 두 알고리즘 모두 각각의 장단점이 있기 때문에 상황에 맞는 알고리즘 선정 필요성이 요구된다.
라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

Dijkstra 알고리즘과 실행시간(Priority Queue를 사용하는 이유)

정의 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘 알고리즈 개요 데이크스트라 알고리즘은 각각의 꼭짓점 v에 대해 s에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 d[s]=0이고, s가 아닌 다른 모든 꼭짓점 v에 대해서는 d[v]=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다. 데이크스트라 알고리즘은 변 경감(edge relaxation)이라고 불리는 기본 연산을 바탕으로 한다. s에서 u까지의 최단 경로(d[u])를 이미 알고 있고, u에서 v까지 길이가 w(u,v)인 변 (u, v)가 존재할 때, s에서 v까지의 최단 경로는 u까지의 최단 경로에 변 (u, v)를 추가함으로써 얻을 수 있다. 이 경로의 비용은 d[u]+w(u, v)가 되며, 이 비용이 현재의 d[v] 값보다 낮으면 d[v]를 새로운 값으로 바꾼다. 경감 연산은 모든 변 (u, v)에 대해 한번씩 경감이 적용되어 모든 d[v]가 최단 경로의 비용을 나타내게 되었을 때 끝난다. 실행시간 개의 변과  {\displaystyle n} 개의  꼭짓점 을 가진  그래프 에 대해  대문자 O 표기법 으로 데이크스트라 알고리즘의 실행시간을 나타낼 수 있다. 가장 간단한 구현으로,  Q 의 집합을  연결 리스트 나  배열  구조로 구현하고 Extract-Min(Q) 함수를 단순한  선형 탐색 으로 구현했을 때 실행 시간은  {\displaystyle O(n^{2})}  시간이 된다. 만약 희소 그래프(sparse graph), 즉  {\displaystyle n^{2}} 보다 훨씬 작은 개수의 변만을 갖는 그래프에 대해서는,...
댓글 쓰기
자세한 내용 보기