[이산수학] 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+이다.
*원하는 자료를 검색 해 보세요.
  • [이산수학] 와샬알고리즘 3페이지
    #include <stdio.h> int sum(int i, int j); // 합집합 계산. Wkik ∪ Wkkj int com(int i, int j); // 교집합 계산. Wkik ∩ Wkkj // 4개의 노..
  • 라우팅 알고리즘 5페이지
    << data >> 7 0 4 5 1000 1000 1000 1000 4 0 6 3 3 1000 1000 5 6 0 4 1000 9 1000 1000 3 4 0 6 3 1000 ......... << shortes..
  • C++을 사용한 all-pair shortest path의 구현 (repreated squ.. 0페이지
    #ifndef __GEOBJECT_H__ #define __GEOBJECT_H__ class GGraph; class GMatrix; //=============================== // Graph..
  • [알고리즘] 플로이드 마샬 10페이지
    using System; using System.Drawing; using System.Collections; using System.ComponentModel; using System.Windows.Forms; ..
  • 오류 역전파 알고리즘-안면인식 알고리즘 26페이지
    1.1 프로젝트 목적 정보화 시대를 걷고 있는 지금 보안의 중요성은 어떤 것 보다 강조 될 수 있다. 하지만 정보의 중요성이 강조 되는 만큼 현대사회에서는 보안을 위협하는 수많은 내외부의 공격에 노출되어 있다. 이러한 위협..
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      [이산수학] Warshall알고리즘