Engineering and Operations Research, University of California, Berkeley. ↑ Stefan Hougardy ( April 2010 ). " The Floyd - Warshall algorithm on graphs with negative cycles ". 《 Information Processing Letters 》 110 ( 8 - 9 ) : 279 - 281. doi : 10. 1016 / j. ipl. 2010. 02. 001. ↑ Gross, Jonathan L. ; Yellen, Jay ( 2003 ), 《 Handbook of Graph Theory 》, Discrete Mathematics and Its Applications, CRC Press, 65쪽, 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
2 ) { displaystyle Omega ( | V | ^ { 2 } ) } 의 변이 있을 수 있고, 모든 변의 조합을 확인하기 때문이다. 이 알고리즘은 두 꼭짓점 간의 추정 최단 경로를 최적이 될 때 까지 점진적으로 개선시켜서 최단경로를 찾는다. 1에서 N { displaystyle N } 까지 번호가 매겨진 V { displaystyle V } 를 꼭짓점으로 갖는 그래프 G { displaystyle G } 를 생각한다. 그 후 i { displaystyle i } 에서 j { displaystyle j } 로 집합 { 1, 2,..., k } { displaystyle { 1, 2, ldots, k } } 의 꼭짓점들 만을 경유지로 거쳐 가는 최단 경로를 반환하는 함수 s h o r t e s t P a t h ( i, j, k ) { displaystyle mathrm { shortestPath } ( i, j, k ) } 를 생각한다. 함수가 주어졌을 때, 목표는 { 1, 2,..., N } { displaystyle { 1, 2, ldots, N } } 에 있는 꼭짓
##하며, i = j { displaystyle i = j } 일 때에도 개선한다. 초기에, 경로 ( i, i ) { displaystyle ( i, i ) } 의 거리는 0이다. 경로 [ i, k,..., i ] { displaystyle [ i, k, ldots, i ] } 는 길이가 0보다 작을 때만 개선이 되므로, 이는 음수 사이클이 존재한다는 것을 의미한다. 그렇기 때문에, 이 알고리즘을 수행한 이후에 ( i, i ) { displaystyle ( i, i ) } 가 음수라면 i { displaystyle i } 에서 i { displaystyle i } 로 되돌아오는 음수 사이클이 존재한다는 것을 의미한다. 따라서, 플로이드 - 워셜 알고리즘을 이용해서 음수 사이클을 감지하기 위해서는, 경로 행렬의 대각 성분을 확인해서 음수가 나타나는지를 확인한다. 음수가 발견되면 적어도 하나 이상의 음수 사이클이 존재한다는 것을 나타낸다. [ 9 ] 수치적 문제를 피하기 위해서는 알고리즘의 안쪽 반복문에서 경로 행렬의 대각 성분에서 음수가 나타나는지를 확인해야 한다. [ 10 ] 무향 그래프에서 음의 가중치가 있으면 그 인접한 꼭짓점 사이에서 음수 사이클
가는 경로 모두 { 1,..., k - 1 } { displaystyle { 1, ldots, k - 1 } } 에 있는 꼭짓점 만을 거쳐간다 ) i { displaystyle i } 에서 j { displaystyle j } 까지 1 { displaystyle 1 } 에서 k - 1 { displaystyle k - 1 } 의 꼭짓점 만을 거쳐가는 경로 중 최선의 경로는 s h o r t e s t P a t h ( i, j, k - 1 ) { displaystyle mathrm { shortestPath } ( i, j, k - 1 ) } 에 의해 정의된다는 것은 알고 있으며, 만약 i { displaystyle i } 에서 k { displaystyle k } 를 거쳐 j { displaystyle j } 로 가는 더 나은 경로가 있다면, 그 경로는 i { displaystyle i } 에서 k { displaystyle k } 까지 ( { 1,..., k - 1 } { displaystyle { 1, ldots, k - 1 } } 만을 거쳐서 ) 가는 경로와 k { displaystyle k } 에서 j { displ
##ump point 크러스컬 Lexicographic BFS LPA * 프림 SMA * 목록 그래프 알고리즘 탐색 알고리즘 그래프 알고리즘의 목록 관련 주제 동적 계획법 그래프 순회 트리 순회 Search game v. d. e. h 컴퓨터 과학에서, 플로이드 - 워셜 알고리즘 ( Floyd - Warshall Algorithm ) 은 변의 가중치가 음이거나 양인 ( 음수 사이클은 없는 ) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. [ 1 ] [ 2 ] 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이 ( 가중치의 합 ) 을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다. 이 알고리즘의 일부 버전은 관계 R { displaystyle R } 의 추이적 폐포를 찾거나, 가중 그래프의 모든 꼭짓점 쌍 간의 최대 폭 경로를 ( 슐츠 선거 제도와 결합해서 ) 찾는 것이 가능하다. 목차 1 역사와 이름 2 알고리즘 3 예시 4 음수 사이클에서 행동 5 경로 복원 6 해석 7 적용과 일반화 8 수행 9 다른 최단 경로 알고리즘과 비교 10 참고 문헌 11 외부 링크 역사와 이름 [ 편집 ] 플로이드 - 워셜 알고리즘은 동적 계획법의 한 예로, 로버트 플로이드가 1962년에 현재 알려진 형태
이루어져 있다는 것을 나타낸다. 경로 [ 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 infinity - 1 infinity 0 k = 1 j 1 2 3 4 i 1 0 infinity - 2 infinity 2 4 0 2 infinity 3 infinity infinity 0 2 4 infinity - 1 infinity 0 k = 2 j 1 2 3 4 i 1 0 infinity - 2 infinity 2 4 0 2 infinity 3 infinity infinity 0 2 4 3 - 1 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 =
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 ] dist [ i ] [ k ] dist [ k ] [ j ] 11 end if 예시 [ 편집 ] 위의 알고리즘은 좌측 하단의 그래프에서 수행된다 : 위에서 첫 번째 외부 반복문의 반복 이전은 k = 0으로 표시했으며, 이것을 통해 알게 된 경로는 그래프의 한 변에 대응한다. 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,
Section 26. 4, " A general framework for solving path problems in directed graphs ", pp. 570 - 576. ↑ Kenneth H. Rosen ( 2003 ). 《 Discrete Mathematics and Its Applications, 5th Edition 》. 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 Wolfgang. " Floyd - Warshall Algorithm ". 《 Wolf
N } { displaystyle { 1, 2, ldots, N } } 에 있는 꼭짓점만을 이용해서 모든 꼭지점 i { displaystyle i } 에서 모든 꼭짓점 j { displaystyle j } 로 가는 최단 경로를 찾는 것이다. 각각의 꼭짓점 쌍에 대해서, s h o r t e s t P a t h ( i, j, k ) { displaystyle mathrm { shortestPath } ( i, j, k ) } 는 다음 중 한 가지에 속한다 : ( 1 ) k { displaystyle k } 를 통과하지 않는 경로 ( 집합 { 1,..., k - 1 } { displaystyle { 1, ldots, k - 1 } } 에 있는 꼭짓점만 거쳐간다. ) ( 2 ) k { displaystyle k } 를 통과 하는 경로 ( i { displaystyle i } 에서 k { displaystyle k } 까지와 k { displaystyle k } 에서 j { displaystyle j } 까지 가는 경로 모두 { 1,..., k - 1 } { displaystyle { 1, ldot
Weisstein, Eric Wolfgang. " Floyd - Warshall Algorithm ". 《 Wolfram MathWorld 》 ( 영어 ). Wolfram Research. ↑ Kleene, S. C. ( 1956 ). 〈 Representation of events in nerve nets and finite automata 〉. C. E. Shannon and J. McCarthy. 《 Automata Studies 》. Princeton University Press. 3 - 42쪽. ↑ Ingerman, Peter Z. ( November 1962 ). " Algorithm 141 : Path Matrix ". 《 Communications of the ACM 》 5 ( 11 ) : 556. doi : 10. 1145 / 368996. 369016. ↑ Hochbaum, Dorit ( 2014 ). " Section 8. 9 : Floyd - Warshall algorithm for all pairs shortest paths " ( PDF ). 《 Lecture Notes for IEOR 266 : Graph Algorithms and Network Flows 》. Department of Industrial Engineering and Operations Research, University of California, Berkeley. ↑ Stefan Hougardy (
컴퓨터 과학에서 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 변의 가중치가 음이거나 양인 (음수 사이클은 없는) 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이(가중치의 합)을 찾는다. 알고리즘 자체는 경로를 반환하지는 않지만, 알고리즘을 약간만 변형시키면 경로를 찾을 수 있다. 이 알고리즘의 일부 버전은 관계 R {\displaystyle R} 의 추이적 폐포를 찾거나, 가중 그래프의 모든 꼭짓점 쌍 간의 최대 폭 경로를 (슐츠 선거 제도와 결합해서) 찾는 것이 가능하다.