[이산수학] 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 int main(void) { int state; int a,cnt1,cnt2; int i,j,k,jj[100],ii[100],kk; //i:행 , j:열 int number,size,Matrix[100][100]; FILE *file..
  • Warshall algorithm 0페이지
    특정한 관계(relation)의 transitive closure를 구하는 Warshall’s algorithm을 구현하시오.1. 테스트 데이터는 파일로부터 읽어들인다. 이때, 테스트 데이터를 위한 파일 이름은 "test.txt"로 한다. 다음은 테스트 데이터 파일 양..
  • [OR 최적화] Floyd 1페이지
    ..FILE:Floyd.txt 0 9 10000 3 10000 10000 10000 10000 9 0 2 10000 7 10000 10000 10000 10000 2 0 2 4 8 6 10000 3 10000 2 0 10000 10000 5 10000 10000 7 4..
  • 라우팅 알고리즘 5페이지
    << routing algorithm >> { bellman-ford 와 floyd-warshall algorithm 중 원하는 방법을 택하여 파일로 노드를 입력받아 결과를 출력하는 프로그램이다. c소스와 노드 입력파일(data.txt), 노드 그림을 담았다 { << ..
  • 알고리즘_워셜 알고리즘_최단경로 5페이지
    - INDEX - Chapter 1. 과제정의 1-1. 과제의 간략한 설명·············································································································..
      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      4. 지식포인트 보유 시 지식포인트가 차감되며
         미보유 시 아이디당 1일 3회만 제공됩니다.
      상세하단 배너
      최근 본 자료더보기
      상세우측 배너
      추천도서
      [이산수학] Warshall알고리즘