플로이드-워셜 알고리즘

플로이드-워셜 알고리즘

학급	전체 쌍 최단 경로 문제(가중치 그래프의 경우)
data 구조	그래프
최악의 경우 성능	${\displaystyle\Theta(V^{3})}$
베스트 케이스 성능	${\displaystyle\Theta(V^{3})}$
평균 성능	${\displaystyle\Theta(V^{3})}$
최악의 경우 공간의 복잡성	${\displaystyle\Theta(V^{2})}$

그래프와 트리 검색 알고리즘
α–β 가지치기 역추적 빔 검색 베스트 퍼스트 검색 브랜치&바운드 폭 우선 검색(BFS) 대영박물관 깊이 우선 검색(DFS) 힐 클라이밍 반복 심화 DFS(IDDFS) 사전 편찬 BFS
최단 경로
A* B* 벨먼-포드 양방향 검색 D* 다이크스트라의 플로이드 워셜 프린지 검색 반복심화(IDA*) 존슨즈 점프 포인트 검색 크루스칼의 라이프 사이클 계획 A* (LPA*) 경로 검색 SMA*
리스트
그래프 알고리즘 검색 알고리즘 그래프 알고리즘 목록
관련 토픽
동적 프로그래밍 그래프 색칠 그래프 트래버설 최소 스패닝 트리 게임 검색 스레드 바이너리 트리 트리 트래버설
v t

컴퓨터 과학에서 플로이드-워셜 알고리즘(플로이드 알고리즘, 로이-워셜 알고리즘, 로이-플로이드 알고리즘, 또는 WFI 알고리즘이라고도 함)은 양의 또는 음의 에지 가중치를 가진 (부정 ^[1][2]사이클이 없는) 유도 가중 그래프에서 최단 경로를 찾는 알고리즘입니다.알고리즘을 한 번 실행하면 모든 정점 쌍 사이의 최단 경로 길이(합계 가중치)를 찾을 수 있습니다.경로 자체에 대한 자세한 내용은 반환되지 않지만 알고리즘을 간단히 수정하여 경로를 재구성할 수 있습니다.알고리즘 버전은 가중 그래프에서 R$(\displaystyle$ R$)$ $관계{\displaystyle }$ 또는 (슐제 투표 시스템과 관련하여) 모든 정점 쌍 사이의 가장 넓은 경로의 과도적 닫힘을 찾는 데도 사용할 수 있습니다.

이력 및 명명

Floyd-Warshall 알고리즘은 동적 프로그래밍의 한 예이며 1962년 ^[3]Robert Floyd에 의해 현재 인식된 형태로 출판되었습니다.그러나 이는 1959년^[4] 버나드 로이가 발표한 알고리즘과 1962년 스티븐^[5] 워셜이 그래프의 ^[6]과도적 닫힘을 찾기 위해 발표한 알고리즘과 본질적으로 동일하며, 결정론적 유한 자동화를 정규식으로 ^[7]변환하기 위한 클린 알고리즘(1956년 발표)과 밀접한 관련이 있다.알고리즘의 현대적 공식은 ^[8]세 개의 중첩된 포루프로서 1962년에 피터 잉거먼에 의해 처음 설명되었다.

알고리즘.

Floyd-Warshall 알고리즘은 각 정점 쌍 사이의 그래프를 통해 가능한 모든 경로를 비교합니다.그래프에 최대 $($2)의 가장자리가 있을 수 있지만 그래프에서 $($3$)\displaystyle$ \$Theta(V ^{3})$ 비교로$$ 이를 수행할 수 있으며 모든 가장자리 조합이 테스트됩니다.이는 추정이 최적화될 때까지 두 꼭지점 사이의 최단 경로에 대한 추정을 점진적으로 개선함으로써 이루어집니다.

1부터$$N까지 $번호$가 매겨진 $꼭지점{\displaystyle }$V$(\$$displaystyle$V$)$의 $그래프{\displaystyle }$$$ G(\$displaystyle$ G$).$ $i$\$style$$$$\$displa로$$ $가능$한 최단 $경로를$반환하는 $함수{\displaystyle \mathrm{}}$ s ${\displaystyle \mathrm{h}}$ ${\displaystyle \mathrm{o}}$ r$$ ${\displaystyle \mathrm{s}}$ ${\displaystyle \mathrm{p}}$ ${\displaystyle \mathrm{a}}$ ${\displaystyle \mathrm{t}}$ $(i,$$$$j$ $k$$)$에 대해 설명합니다.$ystyle$ j$}$은(는) 세트${\displaystyle }${${\displaystyle 1,2}$,$$ k$$}({displaystyle $\1,$ 2,\$ldots,k\})$의 정점만 중간 지점으로 사용합니다.이 함수가 주어졌을 때 우리의 목표는 {${\displaystyle 1}$,${\displaystyle 2}$,${\displaystyle \dots ,}$ $}({displaystyle \$1$, 2,$ \$ldots, N$의 정점을 사용하여 각 $i{\displaystyle }$$(\displaystyle$i)에서 각 j$$$(\displaystyle$ j$)$까지의 최단 경로를 찾는 것입니다.

각 정점 쌍에 대해 s ${\displaystyle \mathrm{h}}$ ${\displaystyle \mathrm{o}}$ r ${\displaystyle \mathrm{e}}$ ${\displaystyle \mathrm{s}}$ ${\displaystyle \mathrm{p}}$ ${\displaystyle \mathrm{a}}$ t ${\displaystyle \mathrm{h}}$( ${\displaystyle i}$, j${\displaystyle }$, ${\displaystyle k}$ $){$ $displaystyle \mathrm {shortestPath}(i , j$ ,$$k )는$$ $다음$ 중 하나입니다$.$

(1) k$({displaystyle$ k$})$를 $통과$하지 않는 경로({${\displaystyle 1}$,${\displaystyle \dots ,\mathrm{k}}$ - 1$}({displaystyle$\{$1,\ldots, k-1\}))$

또는

(2) k$($$i\displaystyle$ i$$$)$에서 $k(\displaystyle$ k$)$로, ${\displaystyle k(\backslash }$$displaystyle$ k$)$에서 j$(\displaystyle$ j$)$로 가는 경로. 둘 다 {$1,\ldots, k-1$의${\displaystyle }$중간 정점만을 사용합니다$.$

$정점{\displaystyle \mathrm{}}$1${\displaystyle (\backslash }$displaystyle$$$$ 1)에서 $k-1$$(\$$displaystyle$ $k-1$$)$까지만 사용하는 i$(\$$displaystyle$ i$)$에서$$j(\$displaystyle j)$로의 최적 경로는 ${\displaystyle \mathrm{s}}$ $, j,$ -$$)에 $의해{\displaystyle \mathrm{}}$ 정의되며, 보다 명확하다면 다음과 같습니다$.$$rom{\displaystyle }$i(\$displaystyle$ i$)$에서$$k$(\$$displaystyle$ j$)$까지 이 경로의 길이는 i$(\displaystyle$ i$)$에서$$k(\$displaystyle$ k$)$까지의 최단 경로({$1, …,$ - 1$\}$의$중간$ 정점만 사용)와 최단 경로의 연결입니다.k$${\$displaystyle$$$k$}$에서$$j {\$displaystyle$ j$}$$$로의 경로({$1$ - $1 }$의 중간 정점만 사용)

w${\displaystyle (i,}$ $)$ {$displaystyle$ w$(i,j$$$$)}$ {${\displaystyle \mathrm{displaystyle}}$ w$($$i$,j)}가$$ $정점{\displaystyle }$ i$\$${\displaystyle \mathrm{displaystyle}}$i\${\displaystyle \mathrm{displaystyle}}$ j$}$와 j$\displaystyle$ a${\displaystyle t}$ $(i$j$$$,$k) 사이의 $가장자리{\displaystyle }$ 무게인 경우, 다음 공식의 기준으로 ${\displaystyle \mathrm{정의}}$할 수 있습니다.

$\displaystyle \mathrm {shortestPath}(i,j,0)=w(i,j)}$

그리고 재귀적인 경우는

$\displaystyle \mathrm {shortestPath} (i,j,k)=}$

${\displaystyle \mathrm {min} {Big ()\mathrm {shortestPath} (i,j,k-1),}$

${\displaystyle \mathrm{s}}$ ${\displaystyle \mathrm{h}}$ ${\displaystyle \mathrm{o}}$ r ${\displaystyle \mathrm{t}}$ ${\displaystyle \mathrm{p}}$ ${\displaystyle \mathrm{a}}$ t${\displaystyle \mathrm{h}}$ (${\displaystyle i}$ ,${\displaystyle k}$ ,${\displaystyle k}$ -${\displaystyle 1}$) + ${\displaystyle s\mathrm{}}$ ${\displaystyle \mathrm{h}}$ ${\displaystyle \mathrm{o}}$ r t ${\displaystyle \mathrm{e}}$ s ${\displaystyle \mathrm{p}}$ ${\displaystyle \mathrm{a}}$ ${\displaystyle \mathrm{t}}$h (${\displaystyle k}$ ,${\displaystyle j}$ ,${\displaystyle k}$ - ${\displaystyle 1}$)${\displaystyle }$( $displaystyle$\ $mathrm${$shortest$Path } ($i$ ,$k$ , k - 1 )$$+ \$mathrm$ { $shortest$Path $}$ ( k , k , k - $1$) { Big$$}$$} 。

이 공식은 Floyd-Warshall 알고리즘의 핵심입니다.이 알고리즘은 k ${\displaystyle =}$ ${\displaystyle 1}$\ $displaystyle$ k $=$ 1 \ $displaystyle$ k = 1 \ displaystyle $($i ,$$$j$,$k$ )의 $모든{\displaystyle }$ $({\displaystyle }$i ,${\displaystyle j}$)$쌍$에 대해 $먼저{\displaystyle }$ ${\displaystyle \mathrm{h}}$ ${\displaystyle \mathrm{o}}$ ${\displaystyle \mathrm{r}}$ ${\displaystyle \mathrm{t}}$ ${\displaystyle \mathrm{e}}$ ${\displaystyle \mathrm{s}}$ ${\displaystyle \mathrm{P}}$ ${\displaystyle \mathrm{a}}$ ${\displaystyle \mathrm{t}}$h (${\displaystyle i}$ ,${\displaystyle j}$ ,${\displaystyle k}$ $){$$displaystyle$$k$$=$의 $순서$로 동작합니다.이 프로세스는 k ${\displaystyle =}$(\$displaystyle$ k$=N$까지 계속되며, 중간 정점을 사용하여 모든${\displaystyle }$(${\displaystyle i,}$j$)\displaystyle(i,j)$ 쌍에$$ 대한 최단 경로를 찾았습니다.이 기본 버전의 의사 코드는 다음과 같습니다.

최소 거리별 dist V×V배열 각 가장자리에(무한대)∞으로 초기화되(u, v)은 가장자리의 무게 // 각 꼭지점 v에(u, v)dist[v][v]k1V에서 나는 1에서 Vj1에서 V만약 dist[나는][j]을에서 0←니← w(u, v)dist[u][v] 하니, dist[나는][k]+dist[k][j]dist자.[나는][j] ← dist[i][k] + dist[k][j] 종료:

예

위의 알고리즘은 아래 왼쪽 그래프에서 실행됩니다.

위의 k = 0으로 표시된 외부 루프의 첫 번째 재귀 이전에 알려진 경로는 그래프의 단일 에지에 해당합니다.k = 1에서, 정점 1을 통과하는 경로가 발견됩니다. 특히, [2,1,3] 경로가 발견되어 가장자리는 적지만 (무게 면에서) 더 긴 경로 [2,3]을 대체합니다.k = 2에서 정점 {1,2}을(를) 통과하는 경로를 찾습니다.빨간색 및 파란색 상자는 교차로에 2가 있는 이전 반복에서 발견된 두 개의 알려진 경로 [4,2] 및 [2,1,3]에서 경로 [4,2,1,3]이 어떻게 조립되는지를 보여줍니다.패스 [4, 2, 3]는 고려되지 않습니다.[2, 1, 3]은 지금까지 발견된 최단 패스이기 때문입니다.k = 3에서 정점 {1,2,3}을(를) 통과하는 경로를 찾습니다.마지막으로, k = 4에서 모든 최단 경로를 찾습니다.

k의 각 반복에서의 거리 행렬은 업데이트된 거리를 굵은 글씨로 표시하면 다음과 같다.

k = 0		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	3	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0

k = 1		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	∞	−1	∞	0

k = 2		j
		1	2	3	4
i	1	0	∞	−2	∞
	2	4	0	2	∞
	3	∞	∞	0	2
	4	3	−1	1	0

k = 3		j
		1	2	3	4
i	1	0	∞	−2	0
	2	4	0	2	4
	3	∞	∞	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$(\displaystyle$i)에서$$j(\$displaystyle$j)까지의$$ 경로 길이는 임의로 작을 수 있기 때문에 음의 사이클의 일부를 구성하는 $정점{\displaystyle }$i(\$displaystyle$ i$)$와$$j(\$displaystyle$ j$)$ 쌍$$ 사이에는 최단 경로가 없습니다.수치적으로 의미 있는 출력을 위해 Floyd-Warshall 알고리즘은 음의 사이클이 없는 것으로 가정합니다.단, 음의 사이클이 있는 경우에는 Floyd-Warshall 알고리즘을 사용하여 검출할 수 있습니다.직관은 다음과 같습니다.

• Floyd-Warshall 알고리즘은 i${\displaystyle }$${\displaystyle =}$ {$displaystyle$$$i$=j$를 포함하여 모든${\displaystyle }$정점 쌍($i$,${\displaystyle }$j$$) $사이$의 경로 길이를 반복적으로 수정합니다.
• 처음에 경로$({\displaystyle i,}$ $)$의 길이는 0입니다.
• 경로 $[{\displaystyle i,}$ ${\displaystyle k,}$ ${\displaystyle \dots ,}$ $]$ {$displaystyle [i,k,\ldots,i]$는 길이가 0보다 작은 경우에만 이를 개선할 수 있습니다. 즉, 마이너스 사이클을 나타냅니다.
• 따라서 알고리즘 후에 ($,$ i) ($i,$ i) ($i,$ i) (displaystyle$)$에서 ($i,$ i$$$)$ ($displaystyle$ i$)$로 돌아가는 음의 길이 경로가 존재하는 경우${\displaystyle }$음이 됩니다.

따라서 Floyd-Warshall 알고리즘을 사용하여 음의 사이클을 검출하려면 패스 매트릭스의 대각선을 조사할 수 있습니다.음수의 존재는 그래프에 적어도1개의 음의 ^[9]사이클이 포함되어 있음을 나타냅니다.알고리즘 실행 중에 음의 사이클이 있는 경우 $\delta {\displaystyle \mathrm{}}$ ${\displaystyle ({\mathrm{}}^{}}$ ${\displaystyle 6^{}}$n - ${\displaystyle 1^{}}$ ${\displaystyle {}^{}{}_{}}$ ${\displaystyle m_{}}$ a${\displaystyle {}_{}}$${\displaystyle x_{}}$$)\displaystyle \Omega$( \$cdot$ 6$^{n-1}w_{max})\$displaystyle $w_{max$})\displaystyle \Omega $(\backslash$$cdot$ 6^{displaystyle w_${$max})\displaystyle ${\displaystyle w_{}}$는 $그래프$에서 음의 최대 절대값입니다.오버플로/언더플로 문제를 방지하려면 알고리즘의 ^[10]내부 for 루프 내에서 경로 매트릭스의 대각선에 음수가 있는지 확인해야 합니다.분명히 무방향 그래프에서 음의 가장자리는 입사 정점을 포함하는 음의 주기(즉, 닫힌 보행)를 생성한다.위 예제 그래프의 모든 모서리를 무방향으로 간주하면, 예를 들어 정점 시퀀스 4 – 2 – 4는 무게 합계가 -2인 주기이다.

경로 재구성

Floyd-Warshall 알고리즘은 일반적으로 모든 정점 쌍 사이의 경로 길이만 제공합니다.간단한 수정으로 두 끝점 정점 사이의 실제 경로를 재구성하는 방법을 만들 수 있습니다.각 정점에서 다른 정점으로 가는 실제 경로를 저장하는 경향이 있을 수 있지만, 이는 필요하지 않으며, 실제로 메모리 측면에서 매우 비용이 많이 듭니다.대신 최단 경로 트리는${\displaystyle }\delta {\displaystyle \mathrm{}}$ ( ${\displaystyle V}$) \$Displaystyle \Theta$$$( V$$)메모리를 사용하여${\displaystyle \delta }$ ( E$$) \$displaystyle \Theta$$$( $E$$$)시간$$ 내에 각 노드에 대해 계산할 수 있습니다.이를 통해 연결된 2개의 정점에서 경로를 효율적으로 재구성할 수 있습니다.

유사 코드

dist를$$V${\displaystyle }$×${\displaystyle }{\displaystyle V}$({$displaystyle$ V \times V$})($무한$)$로 초기화된 최소 거리 배열로 하고 다음으로 V${\displaystyle }$×${\displaystyle }{\displaystyle V}$({$displaystyle$V \$times$ V$})$를 null 프로시저 FloydWarshallWithPathReConstruction()로 초기화된 정점 인덱스의 배열로 합니다(vu).do dist[u] ← w(u, v) // 각 정점에 대한 모서리(u, v) next[u][v] ← 0 next[v] ← 1에서 V do [v] ← 1에서 V까지 k에 대한 v//1에서 V까지 표준 Floyd-War 구현dist[i][j] ← dist[i][k] + dist[k][j] next[i][j] ← next[i][k]

절차 경로(u, v) next[u][v] = null인 경우 경로 ← [u]를 반환하고 u u v ← next[u][v] 경로.path.darg(u) 반환 경로

시간 분석

n$(\displaystyle$n$)$을 V$displaystyle$ V$)$로 $합니다{\displaystyle }$. 이는 정점의 수입니다.${\displaystyle \mathrm{s}}$ ${\displaystyle \mathrm{h}}$${\displaystyle \mathrm{o}}$ r ${\displaystyle \mathrm{t}}$ ${\displaystyle \mathrm{t}\mathrm{p}}$의 $(\$ n$^{2})$를 ${\displaystyle \mathrm{모두}}$ 찾으려면 , ,${\displaystyle }$, , , ,${\displaystyle }$, , , , , , , , , , ${\displaystyle \mathrm{style}}$ \$mathrm${$shortestPath$}($$$i, j$${\displaystyle ,}$$$k$)($$모든{\displaystyle }$ i$\displaystyle$i)와$$j(\$displaystyle$$$j$)$를 $사용$합니다${\displaystyle .}$${\displaystyle {n\mathrm{}}^{}}$ 2$({$의 동작.${\displaystyle \mathrm{s}}$ ${\displaystyle \mathrm{h}}$ ${\displaystyle \mathrm{o}}$ ${\displaystyle \mathrm{r}}$ ${\displaystyle \mathrm{t}}$ ${\displaystyle \mathrm{t}}$ ${\displaystyle \mathrm{P}}$ a ${\displaystyle \mathrm{t}}$h (${\displaystyle i}$ ,${\displaystyle j}$ ,${\displaystyle 0}$ ) ${\displaystyle =}$ ${\displaystyle e\mathrm{}}$ ${\displaystyle \mathrm{d}}$ ${\displaystyle \mathrm{g}}$ ${\displaystyle \mathrm{e}}$ ${\displaystyle \mathrm{C}}$ ${\displaystyle \mathrm{o}}$ s${\displaystyle \mathrm{t}}$ (${\displaystyle i}$ ,$j$) { $displaystyle$\ $mathrm${$shortest$ Path } ($i$ ,$j$ ) = \ $mathrm${ $Edge$Cost } ($i$ ,$j$ ) } s$$ {\ {\ {\ compute compute {\ n \ $displaystyle$ n$$、 ${\displaystyle \mathrm{h}}$ 、 h 、 ${\displaystyle \mathrm{trmatrix}}$ ${\displaystyle \mathrm{h}}$ ${\displaystyle \mathrm{r<img\; alt="n"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b"\; style="vertical-align:\; -0.338ex;\; width:1.395ex;\; height:1.676ex;">}}$ ${\displaystyle \mathrm{since}}$ since since since since since $since{\displaystyle }$ since since since since since since s s s s h 、 h 、 h 、 t t t t ${\displaystyle \mathrm{t}}$ 、 t t t${\displaystyle \mathrm{t}}$ p ${\displaystyle \mathrm{a}}$ ${\displaystyle \mathrm{t}}$h (${\displaystyle i}$ ,${\displaystyle j}$ , $){$ $displaystyle \mathrm${ $shortestPath$$}$ ($$$i$ ,$$${\displaystyle j}$ , ${\displaystyle 2}$$$)$$$、$ $...,$ ${\displaystyle \mathrm{s}}$ h ${\displaystyle \mathrm{o}}$ ${\displaystyle \mathrm{r}}$ ${\displaystyle \mathrm{t}}$ ${\displaystyle \mathrm{e}}$ ${\displaystyle \mathrm{s}}$ p ${\displaystyle \mathrm{a}t}$ h${\displaystyle }$( $i$, j${\displaystyle }$, n $){$ $displaystyle \mathrm${$shortestPath }$ ( i ,$$j , n )2 $.$ n ${\displaystyle {is\mathrm{}}^{}}$ ${\displaystyle \mathrm{is}}$ is is${\displaystyle }$。알고리즘은${\displaystyle }\delta {\displaystyle \mathrm{}}$ (${\displaystyle {n\mathrm{}}^{}}$3)$$\$displaystyle \Theta (n^{3})$ 입니다$.$

응용 프로그램 및 일반화

Floyd-Warshall 알고리즘을 사용하여 다음과 같은 문제를 해결할 수 있습니다.

• 유도 그래프의 최단 경로(플로이드 알고리즘).
• 방향 그래프의 전이적 폐쇄(워셜 알고리즘).Warshall의 알고리즘의 원래 공식에서 그래프는 가중치가 부여되지 않으며 부울 인접 행렬로 표현된다.그런 다음 추가 연산은 논리적 결합(AND)으로 대체되고 최소 연산은 논리적 분리(OR)로 대체됩니다.
• 유한 오토마톤에 의해 받아들여진 정규 언어를 나타내는 정규 표현 찾기(Kleene 알고리즘, ^[12]Floyd-Warshall 알고리즘의 밀접하게 관련된 일반화)
• 실행렬의 반전(가우스-요르단 알고리즘)
• 최적의 라우팅이 응용 프로그램에서는 두 정점 사이의 흐름이 최대인 경로를 찾는 데 관심이 있습니다.즉, 위의 의사 코드에서와 같이 최소값을 취하는 대신 최대값을 취하는 것입니다.가장자리 가중치는 흐름의 고정 구속조건을 나타냅니다.경로의 가중치는 병목현상을 나타내므로 위의 추가 조작은 최소 조작으로 대체됩니다.
• 패스파인더 네트워크의 고속 계산.
• 가장 넓은 경로/최대 대역폭 경로
• 차분 바운드 매트릭스(DBM)의 표준 형식 계산
• 그래프 간의 유사성 계산
• AND/OR/^[14]임계값 그래프의 전이적 폐쇄입니다.

실장

구현은 많은 프로그래밍 언어에 사용할 수 있습니다.

• C++의 경우 부스트::그래프 라이브러리
• C#의 경우 QuickGraph에서
• C#의 경우 QuickGraphPCL(Portable Class Libraries를 사용하는 프로젝트와 더 나은 호환성을 갖춘 QuickGraph의 포크).
• Java의 경우 Apache Commons Graph 라이브러리에서
• JavaScript의 경우 Cytoscape 라이브러리에서
• Julia의 경우 Graphs.jl 패키지
• MATLAB의 경우 Matlab_bgl 패키지로
• Perl의 경우 Graph 모듈에서
• Python의 경우 SciPy 라이브러리(module scipy.sparse.csgraph) 또는 NetworkX 라이브러리
• R의 경우 패키지 e1071 및 Rfast로

다른 최단 경로 알고리즘과의 비교

Floyd-Warshall 알고리즘은 대부분의 또는 모든 정점 쌍이 가장자리로 연결되는 밀도 그래프의 모든 정점 쌍 사이의 경로를 계산하는 데 적합합니다.음수가 아닌 에지 가중치를 갖는 스파스 그래프의 경우, 파이버ACI를 사용하여 Dijkstra(${\displaystyle }$(${\displaystyle E}$V + ${\displaystyle {}^{\mathrm{}}}$ ${\displaystyle 2}$ log${\displaystyle v}$V$)\displaystyle$ O$(E$V + V$^2}\log$ V$)$의 최악의 실행 시간이므로 가능한 각 시작 정점에서 Dijkstra의 알고리즘을 실행함으로써 점근 복잡도를 낮출 수 있다.${\displaystyle )}$는 E {\$displaystyle$ E$$ $}$가 V$$보다 현저히 $작을$ 때 $Floyd-Warshall$ 알고리즘의 O$(\displaystyle$ O$(V$$^{$$3$$\})$보다 작습니다. 음의 가장자리가 있지만 음의 주기가 없는 스파스 그래프의 경우 Johnson 알고리즘을 사용할 수 있습니다.반복된 Dijkstra 접근법과 동일한 점근적 실행 시간.

또한 고밀도 그래프에서 모든 쌍의 최단 경로 계산 속도를 높이기 위해 고속 행렬 곱셈을 사용하는 알려진 알고리즘도 있지만, 일반적으로 에지 가중치에 대한 추가 가정(예: 작은 ^[15][16]정수여야 함)이 있다.또한 실행 시간의 높은 상수 요인 때문에 매우 큰 그래프에 대해 Floyd-Warshall 알고리즘보다 속도를 높일 수 있을 뿐이다.

레퍼런스

외부 링크

• Floyd-Warshall 알고리즘의 인터랙티브 애니메이션
• Floyd-Warshall 알고리즘의 인터랙티브 애니메이션(Munich Technical University of Munich)