알고리즘 공부 <13> - 최단경로 - ALL PAIRS

오늘은 지난번에 공부했던 최단 경로에서 Single vertex가 아닌 All Pairs를 기준으로 공부하려 한다. 또 이를 그리디 알고리즘이라고 한다.

1. All-Pairs Shortest Paths

즉 각노드에 대해서 전부 알고리즘을 수행하는 것이다.

따라서 각각 빅오O 에 대하여 V를 곱해주어야 한다.

자 그럼 한번 자세히보자

노드의 개수 V는 n개일 때 인접 행렬은 nxn 행렬이 된다.

그리고 각각 노드간 간선은 가중치가 있다.

이를 다이나믹 프로그래밍 방법으로 해결하는데 

여기서 우리가 전에 증명한 최단 경로의 모든 서브 경로는 최단 경로이다를 이용한다.

Let p: a shortest path p from vertex i to j that contains at most m edges 

라고 할 때

i 에서 j 로가는 최단경로p는 최대 m개의 간선을 갖는다고 한다. 이때 i -> k 는 m-1개의 엣지를 갖는다.

즉

 *) lij(m) : 최대 m개의 간선을 갖는 I ~ J 까지의 최단경로를 뜻한다.

따라서 lij(m) 를 구하면

m =0 일 때 경로는 존재하지 않으면 접근할 수 없으므로 무한대가 되고 만약 자기 자신이라면 0 이된다.

m>=1 일 때 그림과 같은 결과가 나온다. 여기서 1<=k<=n은 노드의 개수를 의미하며 이는 모든 노드의 대해서 모든 경우를 찾는것을 말한다.

그리고 k가 j일 때는 Wjj 는 0이 되므로 위와같이 정리 되어진다.

---

이제는 이를 이용해서 최단거리를 계산해보자.

그래프가 위와 같이 사이클이 없다면 모든 최단거리는 최대 n-1개의 간선들을 가진다.  이를 이용하여 2차 배열을 통해 최단거리를 구해보자.

이를 이용하여 i와 j는 고정 되어 있고 i행 k열 + k행 j열을 더한 값중 최소 값을 다음 2차배열에 적는 것이다. 즉 이를 의사코드로 보게된다면

 

와 같다. 즉 n^3이 걸리는 EXTEND를 총 n-1번 수행하게 되므로 빅오는 n^4이 된다.

예 :

이를 n-1번,즉 4번 수행해야한다. ( L(4) )

이러한 컨셉으로 만들어진 알고리즘이 Floyd-Warshall Algorithm이다.

위와 같은 계산을 재귀적으로 수행하게 된다.

여기에는 몇가지 가정이 필요하다.

1. 방향이 있는 가중치 그래프이며

2. 음의 가중치가 존재할 수 있고

3. 그래프에는 음의 가중치 사이클이 존재하지 않아야 한다.

모든 노드들에 대한 최단경로들을 구한다.

또 intermediate vertext에 대해서 짚고 넘어가겠습니다.

즉 n-2개의 intermediate 노드가 존재한다.

또 이를 표현하면

d의 의미를 살펴보면 i 부터 j 까지 1부터 k까지의 intermidiate 노드들을 거져처 가는 최단경로를 의미한다.

지금부터 이를 이용해여 플로이드 알고리즘을 보일 것인데 아까의 컨셉을 잘 생각하기를 바란다.

아까 i 행 k열 과 k행 j열을 더 해주던 컨셉과 비슷한데 그전에 하나 정리하고 가겠다.

자 이와같이 k=0 즉 intermediate 노드를 가지지 않을 때는 곧 두 노드의 간선의 가중치가 되고 k가 intermediate가 아니게 될 때(즉,경로가 존재하지 않는 경우)는 이전 d값을 가지게 된다.

CASE 2를 잘보면 이전 컨셉과 비슷한건 알 수있다. 즉 재귀적으로 실행하게 된다

정리한 그림은 위와 같다.  즉 i,k와 k,j을 더해서 최소값일 경우 바꿔주면 된다.

자 한번 예를 보면 된다.

이를 5개의 노드만큼 즉 D(5) 까지 수행하면 된다. 

이번에 이에 대한 빅오를 알아보면 

하나의 행렬 즉 n^2을 수행하는 것을 노드 n개만큼 수행하므로 빅오는 n^3이 된다.