[이산수학] Warshall알고리즘

목차

1. Warshall 알고리즘의 이해
2. 알고리즘의 설계
3. 구현
4. 검증
5. 후기

본문내용

『 집합 {v1,v2,v3..vn}상에서 관계 R을 위한 유향 그래프에서 vi에서 vj 경로 사이에 중간절점들이 {v1,v2,v3..vn}에 속할 경우에, 행렬의 (i,j)차 요소가 1이 되는 행렬을 W=[Wij(k)]라 하자. 이때, Wij(k)=Wij(k-1) ∨(Wik(k-1)∧Wkj(k-1))이다. 여기서 i,j,k는 n보다 작거나 같다. 』
-> Wij(k)1=1 이 될 경우는, 두가지이다.
① Vi에서 Vj까지 경로에서 중간절점들이 {v1,v2,v3..vn}에 포함되면, Wij(k)=1이된다.
② vi에서 vj 경로 사이에 vk 가 첨가되면, vi에서 vk까지의 경로 사이에 중간절점들은 당연히 {v1,v2,v3,...,vk-1}에 속하기 때문에 Wik(k-1)=1이다. 또, vk에서 vj 사이에 중간절점들은 {v1,v2,v3,...,vk-1}에 속하기 때문에 Wkj(k-1)=1이다. 그러므로 vi에서 vj 까지의 경로에 vk 가 추가된 경로가 존재하면 Wij(k)=1이된다.
-> 시작과 끝절점이 v1,v2,v3..vn에 속하지 않으면, 결국 k=n이면 Wn=MR+이다.

참고 자료

없음