플로이드 - 워셜 알고리즘 ( Floyd - Warshall Algorithm ) 은 변의 가중치가 음이거나 양인 ( 음수 사이클은 없는 ) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. [ 1 ] [ 2 ] 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이 ( 가중치의 합 ) 을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다. 이 알고리즘의 일부 버전은 관계 R { [UNK] displaystyle R } 의 추이적 폐포를 찾거나, 가중 그래프의 모든 꼭짓점 쌍 간의 최대 폭 경로를 ( 슐츠 선거 제도와 결합해서 ) 찾는 것이 가능하다. 목차 1 역사와 이름 2 알고리즘 3 예시 4 음수 사이클에서 행동 5 경로 복원 6 해석 7 적용과 일반화 8 수행 9 다른 최단
복잡도 [UNK] ( | V | 2 ) { [UNK] displaystyle [UNK] Theta ( | V | ^ { 2 } ) } 그래프와 트리탐색 알고리즘 alpha - beta A * B * 퇴각검색 빔 벨먼 - 포드 최상 우선 양방향 [UNK] 분기 판정법 BFS 영국박물관 D * DFS 데이크스트라 에드먼즈 플로이드 - 워셜 Fringe search 언덕등반기법 IDA * 반복적 깊이심화 존슨 Jump point 크러스컬 Lexicographic BFS LPA * 프림 SMA * 목록 그래프 알고리즘 탐색 알고리즘 그래프 알고리즘의 목록 관련 주제 동적 계획법 그래프 순회 트리 순회 Search game v. d. e. h 컴퓨터 과학에서, 플로이드 - 워셜 알고리즘 ( Floyd - Warshall Algorithm ) 은 변의 가중치가 음이거나 양인 ( 음수 사이클은 없
지만 음수 사이클은 없는 경우에는 존슨 알고리즘은 수행 시간이 반복 데이크스트라 시간과 같으므로 사용할 수 있다. 알려진 알고리즘 중에는 밀집 그래프에서 모든 쌍의 최단 경로 계산을 빠르게 하기 위해 빠른 행렬 곱셈을 사용하는 알고리즘도 있지만, 이러한 알고리즘들은 변의 가중치에 추가적인 제약 조건이 따른다 ( 예를 들면 작은 정수여야 한다라는 식으로 ). [ 13 ] [ 14 ] 게다가, 수행 시간에서 큰 상수 인자 때문에, 이런 알고리즘들은 매우 큰 그래프에서만 플로이드 - 워셜 알고리즘보다 빠른 속도를 낼 수 있다. 참고 문헌 [ 편집 ] ↑ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ( 1990 ). 《 Introduction to Algorithms 》 1판. MIT Press and McGraw - Hill
알고리즘의 원래 공식에서, 그래프는 가중치가 없고 진릿값 인접 행렬로 나타냈었다. 그리고 덧셈 연산 대신에 논리곱 ( AND ) 이, [UNK] 연산을 논리합 ( OR ) 으로 사용했었다. 유한 오토마타에서 받아들이는 정규 언어를 나타내는 정규식 찾기 ( 클레이니 알고리즘, 플로이드 - 워셜 알고리즘의 밀접한 일반화 ) [ 11 ] 실행렬의 역행렬 ( 가우스 요르단 알고리즘 ) [ 12 ] 최적 라우팅. 이 적용에서는 두 꼭짓점 간의 최대 흐름을 찾는것이 목표이다. 즉, 위의 의사코드에서 최솟값을 적용하는 것이 아니라 최댓값을 적용해야 한다는 것이다. 변의 가중치는 흐름의 제약을 나타낸다. 경로의 가중치는 병목을 나타내므로 위의 덧셈 연산은 [UNK] 연산으로 대체한다. Pathfinder network의 빠른 계산. 최대 폭 경로
1 0 k = 3 j 1 2 3 4 i 1 0 infinity - 2 0 2 4 0 2 4 3 infinity infinity 0 2 4 3 - 1 1 0 k = 4 j 1 2 3 4 i 1 0 - 1 - 2 0 2 4 0 2 4 3 5 1 0 2 4 3 - 1 1 0 음수 사이클에서 행동 [ 편집 ] 음수 사이클은 변의 가중치의 합이 음수를 갖는 사이클이다. 음수 사이클을 구성하는 어떤 꼭짓점 쌍 i { [UNK] displaystyle i }, j { [UNK] displaystyle j } 에 대해서든지 i { [UNK] displaystyle i } 에서 j { [UNK] displaystyle j } 로 가는 경로의 길이는 음의 무한으로 내려갈 수 있기 때문에 최단 경로가 존재하지 않는다. 수치적으로 의미있는 결과를 얻기 위해서, 플로이드 - 워
이 공식은 플로이드 - 워셜 알고리즘의 핵심이다. 이 알고리즘은 처음에 모든 ( i, j ) { [UNK] displaystyle ( i, j ) } 쌍에 대해서 k = 1 { [UNK] displaystyle k = 1 } 일 때 s h o r t e s t P a t h ( i, j, k ) { [UNK] displaystyle [UNK] mathrm { shortestPath } ( i, j, k ) } 를 계산하고, 다음으로 k = 2 { [UNK] displaystyle k = 2 } 일 때를 계산하는 식으로 k = N { [UNK] displaystyle k = N } 이 될 때까지 계속하면, 모든 ( i, j ) { [UNK] displaystyle ( i, j ) } 쌍에 대해서 최단 경로를 찾게 된다. 기본적인 알고리즘의 의사코드는 다음과 같다 : 1 let dist be
j ] > dist [ i ] [ k ] dist [ k ] [ j ] 10 dist [ i ] [ j ] [UNK] dist [ i ] [ k ] dist [ k ] [ j ] 11 end if 예시 [ 편집 ] 위의 알고리즘은 좌측 하단의 그래프에서 수행된다 : 위에서 첫 번째 외부 반복문의 반복 이전은 k = 0으로 표시했으며, 이것을 통해 알게 된 경로는 그래프의 한 변에 대응한다. k = 1일 때, 꼭짓점 1을 통과하는 경로를 찾을 수 있다 : 특히, 경로 [ 2, 1, 3 ] 을 찾았기 때문에, 변이 더 적지만 더 ( 가중치의 관점에서 ) 긴 경로인 [ 2, 3 ] 을 대체한다. k = 2일 때, 꼭짓점 { 1, 2 } 를 통과하는 경로를 찾았다. 빨간 색과 파란 색의 네모는 경로 [
aph 라이브러리 자바스크립트 : Cytoscape 라이브러리 MATLAB : Matlab - bgl 패키지 펄 : Graph 모듈 파이썬 : SciPy 라이브러리 ( 모듈 scipy. sparse. csgraph ) 또는 NetworkX 라이브러리 R : 패키지 e1071과 Rfast 다른 최단 경로 알고리즘과 비교 [ 편집 ] 플로이드 - 워셜 알고리즘은 거의 대부분이나 모든 꼭짓점 쌍이 변으로 연결된 밀집 그래프에서 모든 꼭짓점 쌍 간의 경로를 계산할 때 적합하다. 음수 가중치가 없는 희소 그래프에서는 모든 꼭짓점에서 출발하는 데이크스트라 알고리즘이 반복 데이크스트라의 수행 시간 ( 피보나치 힙을 사용하면 O ( | E | | V | | V | 2 log | V | ) ( | E | | V | | V | 2 log | V |
k } 에서 j { [UNK] displaystyle j } 까지 ( { 1,..., k - 1 } { [UNK] displaystyle [UNK] { 1, [UNK] ldots, k - 1 [UNK] } } 만을 거쳐서 ) 가는 경로를 합친 것이라는 것은 자명하다. w ( i, j ) { [UNK] displaystyle w ( i, j ) } 이 꼭짓점 i { [UNK] displaystyle i } 와 j { [UNK] displaystyle j } 간의 변의 가중치라면, s h o r t e s t P a t h ( i, j, k ) { [UNK] displaystyle [UNK] mathrm { shortestPath } ( i, j, k ) } 를 다음의 재귀적 공식으로 정의할 수 있다 : 기본적인 경우는 s h o r t e s t P a t h ( i, j,
Addison Wesley. ISBN 0 - 07 - 119881 - 4. ↑ Floyd, Robert W. ( June 1962 ). " Algorithm 97 : Shortest Path ". 《 Communications of the ACM 》 5 ( 6 ) : 345. doi : 10. 1145 / 367766. 368168. ↑ Roy, Bernard ( 1959 ). " Transitivite et connexite. ". 《 C. R. Acad. Sci. Paris 》 249 : 216 - 218. ↑ Warshall, Stephen ( January 1962 ). " A theorem on Boolean matrices ". 《 Journal of the ACM 》 9 ( 1 ) : 11 - 12. doi : 10. 1145 / 321105. 321107. ↑ Weisstein, Eric W
컴퓨터 과학에서 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다. 이 알고리즘의 일부 버전은 관계 R {\displaystyle R} 의 추이적 폐포를 찾거나, 가중 그래프의 모든 꼭짓점 쌍 간의 최대 폭 경로를 (슐츠 선거 제도와 결합해서) 찾는 것이 가능하다.