플로이드-워셜 알고리즘 증명

* 스스로 증명한 것이라 틀린 부분이 있을 수도 있습니다

 

플로이드 워셜 알고리즘의 알고리즘을 보면

D는 N*N의 2차원 리스트.
사이에 간선이 있는 두 점 i, j는 D[i][j]에 둘을 간선들 중 최소 길이를 저장.
그렇지 않은 두 점은 D[i][j]에 매우 큰 수(무한에 대응)를 저장

경유점 k를 1부터 N까지:
    시작점 i를 1부터 N까지:
        도착점 j를 1부터 N까지:
            D[i][j] = min(D[i][j], D[i][k]+D[k][1])

과 같다. k가 x일 때(x는 1, 2, ... N) x단계라고 하자. 0단계는 알고리즘을 아예 적용하지 않은 상황으로 하자.

그리고 다음 명제를 P(k)로 두자.

k단계까지 알고리즘을 시행했을 때 D[i][j]는 i부터 j까지 1부터 k까지의 경유점만을 사용할 때의 최단거리 (k = 0, 1, 2, ... N)

이에 대해서 귀납법을 사용하자. (Dynamic Programming과 닮았다는 점에서 착안) 그리고 위의 알고리즘에서 D[i][j] = min(D[i][j], D[i][k] + D[k][j])을 그대로 식에 사용하면 혼란이 생길 수 있으므로 $D_{k+1}[i][j] = min(D_k[i][j], D_k[i][k] + D_k[k][j])$로 표현하겠다. ($D_k[i][j]$는 1에서 k까지만을 경유점으로 사용하는 최단경로라는 의미)

 

1. P(0)의 성립

k = 0이므로 어떤 두 점도 경유점을 거쳐 연결되지 않았다. 따라서 D의 초기 정의에 의하여 둘 사이에 간선만이 둘 사이의 경로가 되므로, 간선으로 연결된 점들은 그 최솟값이 D[i][j]에 연결되므로 성립한다.

 

2. P(k)가 성립할 때 P(k+1)의 성립

$D_{k+1}[i][j] = min(D_k[i][j], D_k[i][k] + D_k[k][j])$에서 min 안의 두 항을 살펴보자. (이때 k+1단계이므로 k에는 k+1을 대입한다.)

$D_k[i][j]$는 k단계까지, 즉 경유점을 1에서 k까지만 사용하는 최단경로다.

$D_k[i][k+1] + D_k[k+1][j]$는 i .... k+1 ... j 로 나타낼 수 있는 최단 경로다. 이때 $D_k[i][k+1]$과 $D_k[k+1][j]$는 각각 1~k까지의 경유점을 사용한 경로의 최솟값을 나타냄을 주의하며 아래를 읽어보자.

 

그럼, 두 점 i와 j 사이에서 1~k+1까지만의 경유점을 사용하는 최단경로는 두 가지 경우가 가능하다.

 

1. k+1을 거치지 않는 최단 경로

$\Rightarrow$ i와 j 사이의 경유점은 P의 정의에 의해 1~k+1까지이므로 k+1이 사용되지 않는다면 1부터 k까지의 경유점들을 사용한 최단 경로이므로 $D_k[i][j]$와 같다. 이때 $D_k[i][j]>D_k[i][k+1]+D_k[k+1][j]$라면 i ... k+1 ... j의 경로는 조건에 맞는 경로이므로 $D_k[i][j]$이 1~k+1의 경유점을 사용할때도 최단경로라는데 모순이다.

따라서 $D_{k+1}[i][j] = min(D_k[i][j], D_k[i][k+1] + D_k[k+1][j]) = D_k[i][j]$

 

2. k+1을 거치는 최단 경로

$\Rightarrow$ i ... k+1 ...  j으로 최단 경로를 표현할 수 있다.

점 i와 j 사이의 최단경로를 i~k+1과 k+1~j로 두 부분으로 나누어주자. 이때 i~k+1, k+1~j는 각각 1~k까지의 경유점들만을 지나는 경로다. 왜냐하면, 만약 이들중에 k+2 이상의 경유점이 있다면, 1~k+1만을 경유하는 최단 경로인 데 모순이다. 또한, 이들 중 k+1을 경유하는 점이 있다면, 위의 최단경로를 i ... k+1 ... k+1 ... j로 표현할 수 있는데, 이때 k+1에서 k+1로 돌아오는 싸이클이 생겨 이 싸이클을 빼면 경로가 더 짧아지므로 최단경로인데 모순이다.

그러면 i~k+1과 k+1~j는 각각 i에서 k+1, k+1에서 j까지의, 1~k까지만을 경유하는 최단경로임을 알 수 있다. 만약 1~k까지만을 경유하는 최단경로가 따로 있다면, 그 경로를 i~k+1 혹은 k+1~j 대신에 넣는 것이 i와 j 사이의 거리를 더 단축시킬 수 있으므로, 원래 경로가 최단경로인데 모순이다. 즉, i~k+1과 k+1~j는 각각 거리가 $D_k[i][k+1]$과 $D_k[k+1][j]$이고, 위의 경로는 $D_{k+1}[i][j] = D_k[i][k+1]+D_k[k+1][j]$로 표현할 수 있다. 역시 $D_k[i][j]<D_k[i][k+1]+D_k[k+1][j]$라면 역시 조건에 맞는 $D_k[i][j]$가 최단경로보다도 작아지게 되어 모순이다.

따라서 $D_{k+1}[i][j] = min(D_k[i][j], D_k[i][k+1] + D_k[k+1][j]) = D_k[i][k+1] + D_k[k+1][j]$

 

이로서 우리는 플로이드 알고리즘이 최단경로를 구해줌을 증명할 수 있다.