ch 언덕등반기법 IDA * 반복적 깊이심화 존슨 Jump point 크러스컬 Lexicographic BFS LPA * 프림 SMA * 목록 그래프 알고리즘 탐색 알고리즘 그래프 알고리즘의 목록 관련 주제 동적 계획법 그래프 순회 트리 순회 Search game v. d. e. h 컴퓨터 과학에서, 플로이드 - 워셜 알고리즘 ( Floyd - Warshall Algorithm ) 은 변의 가중치가 음이거나 양인 ( 음수 사이클은 없는 ) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. [ 1 ] [ 2 ] 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이 ( 가중치의 합 ) 을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다. 이 알고리즘의 일부 버전은 관계 R { [UNK] displaystyle R } 의 추이적 폐포를 찾거나, 가중 그래프의 모든 꼭짓점 쌍 간의 최대 폭 경로를 ( 슐츠 선거 제도와 결합해서 ) 찾는 것이 가능하다. 목차 1 역사와 이름 2 알고리즘 3 예시 4 음수 사이클에서 행동 5 경로 복원 6 해석 7 적용과 일반화 8 수행 9 다른 최단 경로 알고리즘과 비교 10 참고 문헌 11 외부 링크 역사와 이름 [ 편집 ] 플로이드 - 워셜 알고리즘은 동적 계획법의
j, n ) { [UNK] displaystyle [UNK] mathrm { shortestPath } ( i, j, n ) } 을 계산했기 때문에, 사용된 전체 연산의 수는 n [UNK] 2 n 2 = 2 n 3 { [UNK] displaystyle n [UNK] cdot 2n ^ { 2 } = 2n ^ { 3 } } 이다. 따라서, 이 알고리즘의 복잡도는 [UNK] ( n 3 ) { [UNK] displaystyle [UNK] Theta ( n ^ { 3 } ) } 이다. 적용과 일반화 [ 편집 ] 플로이드 - 워셜 알고리즘은 다음의 문제들을 다른 알고리즘과 같이 해결할 수 있다 : 유향 그래프에서 최단 경로 ( 플로이드 알고리즘 ). 유향 그래프의 추이적 폐포 ( 워셜 알고리즘 ). 워셜 알고리즘의 원래 공식에서, 그래프는 가중치가 없고 진릿값 인접 행렬로 나타냈었다. 그리고 덧셈 연산 대신에 논리곱 ( AND ) 이, [UNK] 연산을 논리합 ( OR ) 으로 사용했었다. 유한 오토마타에서 받아들이는 정규 언어를 나타내는 정규식 찾기 ( 클레이니 알고리즘, 플로이드 - 워셜 알고리즘의 밀접한 일반화 ) [ 11 ] 실행렬의 역행렬 ( 가우스 요르단 알고리즘 ) [ 12 ] 최적 라우팅. 이 적용에서는 두 꼭짓점 간의 최대 흐름을 찾는것이 목표이다.
| ^ { 2 } } 에 비해 무시할 수 있을 정도면 플로이드 - 워셜 알고리즘의 수행 시간인 O ( | V | 3 ) { [UNK] displaystyle O ( | V | ^ { 3 } ) } 보다 적으므로 더 적합하다. 희소 그래프에서 음수 가중치가 있지만 음수 사이클은 없는 경우에는 존슨 알고리즘은 수행 시간이 반복 데이크스트라 시간과 같으므로 사용할 수 있다. 알려진 알고리즘 중에는 밀집 그래프에서 모든 쌍의 최단 경로 계산을 빠르게 하기 위해 빠른 행렬 곱셈을 사용하는 알고리즘도 있지만, 이러한 알고리즘들은 변의 가중치에 추가적인 제약 조건이 따른다 ( 예를 들면 작은 정수여야 한다라는 식으로 ). [ 13 ] [ 14 ] 게다가, 수행 시간에서 큰 상수 인자 때문에, 이런 알고리즘들은 매우 큰 그래프에서만 플로이드 - 워셜 알고리즘보다 빠른 속도를 낼 수 있다. 참고 문헌 [ 편집 ] ↑ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ( 1990 ). 《 Introduction to Algorithms 》 1판. MIT Press and McGraw - Hill. ISBN 0 - 262 - 03141 - 8. See in particular Section 26. 2, " The Floyd - Warsh
V | 3 ) { [UNK] displaystyle [UNK] Theta ( | V | ^ { 3 } ) } 의 비교로 진행할 수 있다. 그 이유는 그래프에서는 최대 [UNK] ( | V | 2 ) { [UNK] displaystyle [UNK] Omega ( | V | ^ { 2 } ) } 의 변이 있을 수 있고, 모든 변의 조합을 확인하기 때문이다. 이 알고리즘은 두 꼭짓점 간의 추정 최단 경로를 최적이 될 때 까지 점진적으로 개선시켜서 최단경로를 찾는다. 1에서 N { [UNK] displaystyle N } 까지 번호가 매겨진 V { [UNK] displaystyle V } 를 꼭짓점으로 갖는 그래프 G { [UNK] displaystyle G } 를 생각한다. 그 후 i { [UNK] displaystyle i } 에서 j { [UNK] displaystyle j } 로 집합 { 1, 2,..., k } { [UNK] displaystyle [UNK] { 1, 2, [UNK] ldots, k [UNK] } } 의 꼭짓점들 만을 경유지로 거쳐 가는 최단 경로를 반환하는 함수 s h o r t e s t P a t h ( i, j, k ) { [UNK] displaystyle [UNK] mathrm { shortestPath } ( i, j, k ) } 를 생각한다. 함수가 주어졌
{ [UNK] displaystyle ( i, j ) } 쌍에 대해서 최단 경로를 찾게 된다. 기본적인 알고리즘의 의사코드는 다음과 같다 : 1 let dist be a | V | x | V | array of minimum distances initialized to infinity ( infinity ) 2 for each edge ( u, v ) 3 dist [ u ] [ v ] [UNK] w ( u, v ) / / 변 ( u, v ) 의 가중치 4 for each vertex v 5 dist [ v ] [ v ] [UNK] 0 6 for k from 1 to | V | 7 for i from 1 to | V | 8 for j from 1 to | V | 9 if dist [ i ] [ 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,
으며, 이것을 통해 알게 된 경로는 그래프의 한 변에 대응한다. k = 1일 때, 꼭짓점 1을 통과하는 경로를 찾을 수 있다 : 특히, 경로 [ 2, 1, 3 ] 을 찾았기 때문에, 변이 더 적지만 더 ( 가중치의 관점에서 ) 긴 경로인 [ 2, 3 ] 을 대체한다. k = 2일 때, 꼭짓점 { 1, 2 } 를 통과하는 경로를 찾았다. 빨간 색과 파란 색의 네모는 경로 [ 4, 2, 1, 3 ] 이 경로 [ 4, 2 ] 와 이전 반복에서 찾은 [ 2, 1, 3 ] 이 2를 교차점으로 결합해서 이루어져 있다는 것을 나타낸다. 경로 [ 4, 2, 3 ] 은 2에서 3까지 가는 경로가 [ 2, 1, 3 ] 보다 길기 때문에 고려하지 않는다. k = 3일 때, { 1, 2, 3 } 을 지나는 경로를 찾는다. 마지막으로, k = 4일 때, 모든 최단경로를 찾게 된다. 각각의 k의 반복에 대한 거리 행렬, 업데이트 된 거리는 굵은 글씨로 표시했다 : k = 0 j 1 2 3 4 i 1 0 infinity - 2 infinity 2 4 0 3 infinity 3 infinity infinity 0 2 4 inf
수 사이클에서 행동 5 경로 복원 6 해석 7 적용과 일반화 8 수행 9 다른 최단 경로 알고리즘과 비교 10 참고 문헌 11 외부 링크 역사와 이름 [ 편집 ] 플로이드 - 워셜 알고리즘은 동적 계획법의 한 예로, 로버트 플로이드가 1962년에 현재 알려진 형태로 발표했다. [ 3 ] 하지만, 이 알고리즘은 본질적으로 버나드 로이가 1959년에 발표한 알고리즘 [ 4 ] 과, 스티븐 워셜이 1962년에 발표한 알고리즘 [ 5 ] 과 그래프의 추이적 폐포를 찾는다는 점, [ 6 ] 그리고 결정적 유한 오토마타를 정규 표현식으로 변환할 때, 클레이니 알고리즘 ( 1956년에 발표됨 ) 과 밀접한 관련이 있다는 점에서 동일하다. [ 7 ] 이 알고리즘의 삼중 for 반복문의 공식은 1962년에 Peter Ingerman이 설명하였다. [ 8 ] 이 알고리즘은 플로이드 알고리즘, 로이 - 워셜 알고리즘, 로이 - 플로이드 알고리즘, 또는 WFI 알고리즘으로 알려져 있다. 알고리즘 [ 편집 ] 플로이드 - 워셜 알고리즘은 각각의 꼭짓점 쌍을 지나는 그래프의 모든 경로를 비교한다. 이 방법은 그래프에서 [UNK] ( | V | 3 ) { [UNK] displaystyle [UNK] Theta ( | V | ^ { 3 } ) } 의 비교로 진행할 수 있다. 그 이유는 그래프에서는 최대 [UNK] ( | V | 2
le i } 에서 k { [UNK] displaystyle k } 를 거쳐 j { [UNK] displaystyle j } 로 가는 더 나은 경로가 있다면, 그 경로는 i { [UNK] displaystyle i } 에서 k { [UNK] displaystyle k } 까지 ( { 1,..., k - 1 } { [UNK] displaystyle [UNK] { 1, [UNK] ldots, k - 1 [UNK] } } 만을 거쳐서 ) 가는 경로와 k { [UNK] displaystyle 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, k, k - 1 ) s h o r t e s t P a t h ( k, j, k - 1 ) ) { [UNK] displaystyle [UNK] mathrm { shortestPath } ( i, k, k - 1 ) [UNK] mathrm { shortestPath } ( k, j, k - 1 ) { [UNK] Big ) } }. 이 공식은 플로이드 - 워셜 알고리즘의 핵심이다. 이 알고리즘은 처음에 모든 ( 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 a | V | x
쪽, ISBN 9780203490204. ↑ Penaloza, Rafael. " Algebraic Structures for Transitive Closure ". ↑ Zwick, Uri ( May 2002 ), " All pairs shortest paths using bridging sets and rectangular matrix multiplication ", 《 Journal of the ACM 》 49 ( 3 ) : 289 - 317, arXiv : cs / 0008011, doi : 10. 1145 / 567112. 567114. ↑ Chan, Timothy M. ( January 2010 ), " More algorithms for all - pairs shortest paths in weighted graphs ", 《 SIAM Journal on Computing 》 39 ( 5 ) : 2075 - 2089, doi : 10. 1137 / 08071990x. 외부 링크 [ 편집 ] 공용에 분류가 있습니다. 플로이드 - 워셜 알고리즘 플로이드 - 워셜 알고리즘의 조작 가능한 애니메이션 원본 주소 " " 분류 : 그래프 알고리즘라우팅 알고리즘다항 시간 문제의사코드가 있는 문서동적 계획법숨은 분류 : CS1 - 영어 인용 ( en ) 영어 표기를 포함한 문서 둘러보기 메뉴 개인 도구 로그인하지
컴퓨터 과학에서 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다. 이 알고리즘의 일부 버전은 관계 R {\displaystyle R} 의 추이적 폐포를 찾거나, 가중 그래프의 모든 꼭짓점 쌍 간의 최대 폭 경로를 (슐츠 선거 제도와 결합해서) 찾는 것이 가능하다.