플로이드-와샬 알고리즘

1. Transitive Closure

 

 

 

: Digraph G가 주어졌을때, u-v사이에 path가 존재하면 u-v사이의 directed edge를 추가한게  G*, transitive closure이다.

 

EX) G에서 B->D->E 를 연결하는 path가 있으면 B->E directed edge를 추가한다.

-> 이는 diagraph에서 reachability information을 제공할 수 있다.

 

 

 

 

 

 

2. Transitive Closure는 어떻게 알 수 있는가?

1) 모든 정점에 대해서 DFS를 수행한다.

O(n(n+m)) -> 정점에서 reachable한 vertex를 찾는 DFS를 모든 정점에 대해서 수행해야 한다.

: 만약 Graph가 Dense하다면 최악의 경우엔 O(n^3), Sparse하다면 O(n^2)시간이 걸릴 수 있다. 

-> heavy한 연산을 계속 하게 된다.

 

2) Dynamic Programming을 사용한다.-> 이 방법이 Floyd-Warshall Algorithm이다.

 

3. Floyd-Warshall Algorithm

: 이 알고리즘은 두가지 idea를 기반으로 하고 있다.

#Idea 1: 각 vertice들을 1,2,...n으로 번호로 관리한다 -> n 단계로 구성되어있음을 알 수 있다.

#Idea 2:  1,2,3,..k 단계에 다다랐을때 1~k vertice까지를 활용해 갈 수 있는 모든 path를 다 찾는다.

 

잘 와닿진 않으니 예를 들어 설명해보자면,

- 각 사람을 vertice로 지정하고, 사람들에게 전화번호부가 존재한다고 가정하자.

- 1번은 3번의 번호를 알지만, 3번은 1번의 번호를 모를수도 있다. 이 관계를 digraph로 표현해보자.

- Floyd-warshall 알고리즘은 사람들 사이의 연락망을 구성하고 싶을때, 매일 한명씩 전화번호부를 공개하는 것과 비슷하다.

-> 따라서 k번째 날에는 k번이 전화번호를 공개하며, 1번~k번의 번호부를 모두 활용하여 k번의 전화번호부까지 reach되는 사람들은 모두 전화번호부 업뎃이 가능하다. 즉, 3번이 자신이 번호를 아는 사람들에게 자기 번호를 공개했을때 3과 관계가 있는 vertice들은 3번의 번호부를 통해 이전엔 몰랐지만 새로운 사람에게 직접적으로 닿을 수 있게 된다.

 

-> 이를 다시 graph로 표현하면, 만약 k번의 관계를 활용하면서 이전엔 몰랐던 i->k,k->j사이의 관계를 알게되어 i->j사이에 path가 생겼다면, 이를 directed edge로 바로 이어주는 것을 의미한다.

 

1) Example

예시를 통해 알아보자.

-> 다음과 같은 그래프가 존재한다고 생각해보자.

노드에게 incoming edge가 들어오면 나의 번호를 아는 사람이고, outcoming edge를 통해 나가면 내가 번호를 아는 사람이라고 생각해보자. 그렇다면, 매일 한명의 전화번호부를 공개하면서 나 자신을 중간지점으로 삼아 다른사람들이 자신의 전화번호부를 업뎃할수 있도록 한다고 생각하면 플로이드 와샬 알고리즘을 쉽게 이해할 수 있다.

 

* 그렇다면 매 열은 나의 번호를 아는 사람들, 매 행은 나의 전화번호부 라고 생각하면 되겠다.

매 단계마다 나의 번호를 아는 사람들(나에게 직접적으로 닿을 수 있는 사람들)이 내 전화번호부를 중간 지점 삼아 다른 번호를 알아간다고 하면, 이 과정을 인접 행렬을 통해 알아보자. 초기 상태는 아래 그래프와 같다.

	1번	2번	3번	4번	5번	6번	7번
1번	0	0	0	1	0	0	0
2번	0	0	0	0	0	0	0
3번	1	1	0	1	0	0	0
4번	0	0	1	0	0	0	0
5번	1	0	1	0	0	0	0
6번	0	1	1	0	1	0	1
7번	0	0	0	0	1	1	0

 

1. 1번이 자신의 전화번호부를 공개했다.

1번의 전화번호부를 아는 사람들은 1열을 살펴보면 3번, 5번이다. 따라서 3->1,5->1 이라는 incoming edge가 존재하는 것이다. 따라서 1번이 중간 지점이 되므로 1번을 통해 4번의 번호를 알수 있게 되는데, 3번은 이미 알고 있고, 5번은 몰랐다. 따라서 5->1->4로 향하는 path가 생긴것이므로 direct edge를 이어준다.

	1번	2번	3번	4번	5번	6번	7번
1번	0	0	0	1	0	0	0
2번	0	0	0	0	0	0	0
3번	1	1	0	1	0	0	0
4번	0	0	1	0	0	0	0
5번	1	0	1	1	0	0	0
6번	0	1	1	0	1	0	1
7번	0	0	0	0	1	1	0

 

2. 2번이 자신의 전화번호부를 공개했다.

기존에 2번의 번호를 알았던 사람은 3번, 6번, 그렇지만 2번은 아는 번호가 없다. pass

 

3. 3번이 자신의 전화번호부를 공개했다.

3번의 번호를 알고 있던 사람은 4번, 5번, 6번. 3번의 전화번호부에 있는 번호는 1,2,4번. 이 사람들의 번호를 차례대로 업뎃해주자.

 

1) 4번 - 4번은 1,2번의 번호를 몰랐다. 따라서 3번이 중간 지점이 되어 4->3->1,4->3->2의 path가 생긴 것이므로 direct edge를 4->1,4->2에 추가해주자.

2) 5번 - 5번은 2번의 번호를 몰랐다. 따라서 3번이 중간 지점이 되어 5->3->2의 path가 생겼으므로 5->2를 추가하자.

3) 6번 - 6번은 기존에 1,4번의 번호를 몰랐다. 따라서 3번의 전화번호부를 이용해 6->1,6->4 path를 추가하자.

 

	1번	2번	3번	4번	5번	6번	7번
1번	0	0	0	1	0	0	0
2번	0	0	0	0	0	0	0
3번	1	1	0	1	0	0	0
4번	1	1	1	0	0	0	0
5번	1	1	1	1	0	0	0
6번	1	1	1	1	1	0	1
7번	0	0	0	0	1	1	0

 

4. 4번이 자신의 전화번호부를 공개했다.

기존에 4번에 닿을 수 있었던 사람은 1,3,5,6번. 4번이 번호를 아는 사람은 1,2,3번.  차례대로 업뎃해주자.

1) 1번 - 1번은 기존에 2,3번의 번호를 몰랐다. 1->2, 1->3을 추가한다.

2) 3,5,6번은 기존에 모두 1,2,3번의 번호를 알고 있다. (3-3은 제외) pass.

 

	1번	2번	3번	4번	5번	6번	7번
1번	0	1	1	1	0	0	0
2번	0	0	0	0	0	0	0
3번	1	1	0	1	0	0	0
4번	1	1	1	0	0	0	0
5번	1	1	1	1	0	0	0
6번	1	1	1	1	1	0	1
7번	0	0	0	0	1	1	0

 

5. 5번이 자신의 전화번호부를 공개했다.

기존에 5번에게 닿을 수 있던 사람은 6,7번, 5번이 번호를 아는 사람은 1,2,3,4번. 차례대로 업뎃해주자

1) 6번- 6번은 이미 1,2,3,4를 모두 알고 있다. pass

2) 7번- 7번은 1,2,3,4번의 번호를 몰랐다. 따라서 7->1,7->2,7->3,7->4의 direct edge를 추가하자.

	1번	2번	3번	4번	5번	6번	7번
1번	0	1	1	1	0	0	0
2번	0	0	0	0	0	0	0
3번	1	1	0	1	0	0	0
4번	1	1	1	0	0	0	0
5번	1	1	1	1	0	0	0
6번	1	1	1	1	1	0	1
7번	1	1	1	1	1	1	0

6. 6번이 자신의 전화번호부를 공개했다.

기존에 6번에게 닿을 수 있던 사람은 7번. 6번이 아는 번호는 1,2,3,4,5,7번.

그렇지만 7번은 이미 그 번호를 모두 안다. pass

 

7. 7번이 자신의 전화번호부를 공개했다. 

기존에 7번에게 닿을수 있던 사람은 6번. 그렇지만 모든 번호를 이미 알고 있으므로 pass.

 

 

따라서 그래프의 최종 결과는 다음과 같다.

	1번	2번	3번	4번	5번	6번	7번
1번	0	1	1	1	0	0	0
2번	0	0	0	0	0	0	0
3번	1	1	0	1	0	0	0
4번	1	1	1	0	0	0	0
5번	1	1	1	1	0	0	0
6번	1	1	1	1	1	0	1
7번	1	1	1	1	1	1	0

 

 

2) Pseudocode

-> 매 그래프가 갱신될때마다 저장해둔 이전의 값을 가지고 새롭게 갱신한다.

1) n 단계를 거쳐 그래프를 갱신한다 

2) 매 그래프는 모든 인접 행렬의 원소를 모두 확인한다. -> n^2

   1) 만약  V(,i,k)를 확인하여 i->k로 향하는 edge가 존재하고,

   2) V(k,j) 를 확인해 k->j로 향하는 edge가 존재하고,

   3) V(i,j)를 확인해 i->j로 향하는 directed edge가 없으면 하나 넣어준다.

 

# 따라서 시간 복잡도는 n * n^2= O(n^3)이다.

 

 

4. All-pairs Shortest Path

Floyd-Warshall Algorithm을 통해 All-pairs Shortest Path 문제를 해결할 수 있다.

n:n shortest path로, 각 정점에서 다른 정점에서 가는 모든 최소path를 구할 수 있다.

->  점화식의 형태는 dijkstra와 동일하다.

식: min(X->Y로 가는 최소비용 , X에서 노드 k로 가는 비용 + 노드 k에서  Y로 가는 비용)

 

다만, 이전 방법과는 달리 인접행렬에서 만약 길을 모르면 0이 아닌 무한대로 초기화해놓는다. 

 

1) Example

다음과 같은 그래프가 존재한다고 가정하자.

0	5	무한	8
7	0	9	무한
2	무한	0	4
무한	무한	3	0

 

-> 이 인접 행렬을 매번 갱신해가자. 점화식을 적용하는 거 말고는 위의 방법과 다를게 없다.

 

1) 1번에게 바로 닿을 수 있는 노드는 2번, 3번이다. 1번이 아는 길은 2번, 4번이다.

  2번 : d[2,4]=무한, d[2,1]+d[1,4]=7+8=15 이다. 따라서 1을 거쳐서 4를 가는게 빠르다. 15로 갱신하자.

  3번 : 3번은 2,4로 가는 길을 갱신하고 싶어한다.

         d[3,2]=무한, d[3,1]+d[1,2]=2+5=7 -> 1번을 거쳐서 2로 가야 한다. 7로 갱신한다.

         d[3,4]=4, d[3,1]+d[1,2]=2+5=7 -> 기존 방법이 더 빠르다. 갱신하지 않는다.

0	5	무한	8
7	0	9	15
2	7	0	4
무한	무한	3	0

 

2) 2번에게 바로 닿을 수 있는 노드는 1번, 3번이다. 2번이 아는 길은 1,3,4번이다.

 1번: d[1,3]=무한, d[1,2]+d[2,3]=5+9=14 -> 갱신

      d[1,4]=8, d[1,2]+d[2,4]=5+15=20-> 갱신x

  3번: d[3,1]=2, d[3,2]+d[2,1]=7+7=14 -> 갱신 X

        d[3,4]=4, d[3,2]+d[2,4]=7+15=22 -> 갱신 X

0	5	14	8
7	0	9	15
2	7	0	4
무한	무한	3	0

 

3) 3번에게 바로 닿을 수 있는 노드는 1,2,4번이다. 3번은 1,2,4번을 향하는 길을 알고 있다.

   1번: d[1,2]=5, d[1,3]+d[3,2]=14+7=21 -> 갱신X

        d[1,4]=8, d[1,3]+d[3,4]=14+4=18 -> 갱신X

   2번: d[2,1]=7, d[2,3]+d[3,1]=9+2=11 -> 갱신X

        d[2,4]=15, d[2,3]+d[3,4]=9+4=13 -> 갱신

   4번: d[4,1]=무한, d[4,3]+d[3,1]=3+2=5 -> 갱신

        d[4,2]=무한, d[4,3]+d[3,2]=3+7=10 -> 갱신

0	5	14	8
7	0	9	13
2	7	0	4
5	10	3	0

 

4) 4번에게 바로 닿을 수 있는 노드는 1,2,3번이다. 4번은 1,2,3번으로 향하는 길을 알고 있다.

1번: d[1,2]=5, d[1,4]+d[4,2]=8+10=18 -> 갱신X

       d[1,3]=14, d[1,4]+d[4,3]=8+3=11 -> 갱신

2번: d[2,1]=7, d[2,4]+d[4,1]=15+5=20 -> 갱신X

      d[2,3]=9, d[2,4]+d[4,3]=15+3=18 -> 갱신X

3번 :d[3,1]=2, d[3,4]+d[4,1]=4+5=9 -> 갱신X

      d[3,2]=7, d[3,4]+d[4,2]=4+10=14 -> 갱신X

 

<최종 결과는 다음과 같다>

0	5	11	8
7	0	9	13
2	7	0	4
5	10	3	0

 

 

2) Pseudocode

-> 기본적으로 floyd-warshall algorithm이므로 O(n^3)이 걸린다. (사실은 이 알고리즘은 원래 n:n shortest path문제를 해결하므로 첫번째보단 두번째 수도코드가 많이 쓰인다.)

= 우리는 매 정점마다 다익스트라 알고리즘을 수행함으로써 같은 문제를 해결할 수 있다. 매번 다익스트라 알고리즘이 O(mlogn) 만큼 걸리므로, 총 O(n*mlogn)만큼의 시간이 소요되지만 dense한 그래프의 경우에 최악의 경우 O(n^3logn)시간이 걸릴수도 있다.  따라서 우리는 n:n shortest path 문제를 풀 때는 플로이드-와샬 알고리즘을 사용한다.