[이산수학] Warshall알고리즘

등록일 2003.11.13 한글 (hwp) | 3페이지 | 가격 1,000원

목차

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+이다.
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      최근 본 자료더보기
      추천도서