플로이드 워셜 알고리즘(그래프 이론, JAVA, V^3, 다이나믹 프로그래밍)

## 기본 정의 및 증명

---

플로이드 워셜 알고리즘은 시간복잡도가 N^3이고, 공간복잡도는 N^2의 알고리즘이다. 알고리즘 구현이나 설명은 매우 간단하다. 

 

 

 

플로이드 워셜 알고리즘의 핵심은 다이나믹 프로그래밍이다. 임의의 두 노드가 있다고 가정해보자, 두 노드는 i와 j라고 하자. 두 노드의 최단 거리는 여러 점들을 경유할 수 있다. 이 점에 착안해서, 다이나믹 프로그래밍이 구현된다.

 

 

 

다이나믹 프로그래밍 알고리즘

 

i와 j사이에 k번 노드까지 경유할 수 있을 때 최소 거리에 대한 공식이다. k - 1번 노드까지 얻어진 거리 혹은 신규로 k번째 노드를 추가해서 얻을 수 있는 거리가 최소 거리가 될 것이다. 추가적으로 설명하자면, i와 j사이의 최단 거리에 k번째 노드가 들어갈 수 있는지 없는지가 핵심이다. 

 

 

 

공간복잡도로 2차원 배열을 사용하면, K번째 노드를 경유한 거리가 최단 거리를 구하는데 이용되지 않을까? 어떤, a, b, c가 있다고 해보자. shortestPath(a, b, c)는 이미 갱신이 된 상태다, 이후에 다른 경로를 구하는 과정에서 shortestPath(a, b, c - 1)를 사용해야 할 때를 생각해보면, b = k여야만 한다.

 

 

 

b를 k로 치환해보자,

shortestPath(a, k, c) = min(shortestPath(a, k, c - 1), shortestPath(a, k, c - 1) + shortestPath(k, k, c - 1)

shortestPath(a, k, c) = min(shortestPath(a, k, c - 1), shortestPath(a, k, c - 1) + 0)

shortestPath(a, k, c) = shortestPath(a, k, c - 1)

 

 

 

위의 식으로 증명된 사실은, a, b, c가 갱신이 되어도, a, b, c - 1의 값을 가진다는 것이다.

 

 

 

또 다른 궁금증이 생겼다. 다이익스트라는 최단 경로를 구할 때, 모든 노드들을 한번만 지나거나 지나지 않는 식으로 경로가 생성된다. 플로이드 워셜 알고리즘은 임의의 노드 두 개 사이에, 경유하는 점들을 추가하는 방식이면 어떤 경유 노드를 2번 이상 지날 수 있지 않을까?

 

 

 

어떤 경유 노드를 2번 이상 지날 수 있을까? 정답은 아니다, 그 경유 노드를 한번만 지나는 것이 더 작기 때문에 절대로 2번 이상 지나는 경유 노드는 존재할 수 없다.

 

 

 

플로이드 최단 거리 경로 찾기

---

플로이드 알고리즘을 통해서 경로를 추적하는 방법을 알아보려고 한다. 알아보려고 하는데, 위키 백과에 잘 나와있어서 위키백과를 통해서 설명을 하겠다.

 

 

 

 

dist[i][j] = i와 j 노드 사이의 최단 거리

next[i][j] = i와 j 사이의 경로의 첫번째 노드(사이의 노드가 존재하지 않을 시 j)

 

 

 

위의 관계로 코드를 이해하면 된다. 첫번째 노드만 갖게 되면, 첫번째 노드와 다시 j 사이의 경로의 첫번째 노드를 찾아가면서, 최단 경로를 완성할 수 있다. 첫번째 노드만을 갖고 있으므로, 공간적으로 효율적이다.

 

 

 

next[u][v]의 경로를 찾고자 한다면, u에서 시작해서, 매번 첫번째 노드를 찾아가면 최종적으로 v까지의 최단 경로를 구할 수 있게 된다.