• LF몰 이벤트
  • 파일시티 이벤트
  • 서울좀비 이벤트
  • 탑툰 이벤트
  • 닥터피엘 이벤트
  • 아이템베이 이벤트
  • 아이템매니아 이벤트

Dijkstra 알고리즘을 ST에 적용

*정*
최초 등록일
2010.02.06
최종 저작일
2009.11
7페이지/한글파일 한컴오피스
가격 1,000원 할인쿠폰받기
다운로드
장바구니

소개글

딕스트리 알고리즘 해석입니다.

목차

1.스페닝 트리의 개념 1
2.스페닝 트리 사용 1
3.최소비용 스페닝 트리 2
4. 구현 방법 2
5. 딕스트라 (dijstra) 적용한 ST를 찾을 때 예제 2
6. 최단 경로를 구하는 과정 6
7. 참고문헌 6

본문내용

1. 스페닝 트리의 개념
- 스페닝 트리(Spanning Tree)는 “신장 트리” 이라고 한다.
- 원래 그래프에서 장점은 그대로이고 간선은 노드의 수보다 1개 적으며 원래 그래프
를 연결된 상태로 만드는 그래프를 말한다.
- 간선의 수가 장점의 수보다 1개 적으므로 그래프에 사이클이 없게 한다.

2. 스페닝 트리 사용
첫째: 경기도 10개 도시의 송유관을 건설한다고 할 때 어떻게 하면 중복시키지 않고(사이클이 없이) 9개 송유관으로 모든 도시를 원류 공급지와 연결을 시킬 것인가? 하는 문제는 그래프에서 스페닝 트리 문제가 된다.

둘째: 건물간의 컴퓨터 네트웍을 연결할 때 사이클이 없이 전체 건물이 연결되도록 통신선을 구성할 것인가가 스페닝 트리 문제가 된다.

3. 최소비용 스페닝 트리(MST: Minimun Cost Spanning Tree)
- 신장트리 중에서 사용된 간선들이 가중치 합이 최소인 트리

ex)
- 도로건설: 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
- 전기회로: 단자들을 모두 연결하면서 전선의 길이가 최소가 되도록 하는 문제
- 통신: 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제

4. 구현 방법
1) Kruscal 방법
- 간선중 비용이 작은 것부터 큰 순으로 소트(5,6,10,11....)
- 가장 작은 비용이 드는 간선부터 차례로 추가(5,6,10....)
- 추가 중 사이클이 존재하는 간선은 제외
- 모든 장점이 연결될 때까지 반복

2) Prim 방법
- 임의의 장점을 선택
- 이 장점에서 다른 장점으로 갈수 있는 최소 비용의 장점을 선택
이 장점은 제외
- 이 장점에서 다른 장점으로 가는 비용과 기존과 비교 후 더 작은 비용이
있으면 갱신
- 2-3번 과정을 n(장점의 수) -1번 반복

참고 자료

[1] TCP/IP Protocol Suit3 3e 김병철 외 공역
[2] 2007년 1학기 2학년 자료구조 그룹발표 6조 참조
[3] 네이버 지식 검색
[4] C언어 쉽게 풀어 쓴 자료구조/ 생능출판사
[5]http://cafe.naver.com/missilewarfare.cafe?iframe_url=/ArticleRead.nhn%3Farticeid=2939
*정*
판매자 유형Bronze개인

주의사항

저작권 자료의 정보 및 내용의 진실성에 대하여 해피캠퍼스는 보증하지 않으며, 해당 정보 및 게시물 저작권과 기타 법적 책임은 자료 등록자에게 있습니다.
자료 및 게시물 내용의 불법적 이용, 무단 전재∙배포는 금지되어 있습니다.
저작권침해, 명예훼손 등 분쟁 요소 발견 시 고객센터의 저작권침해 신고센터를 이용해 주시기 바랍니다.
환불정책

해피캠퍼스는 구매자와 판매자 모두가 만족하는 서비스가 되도록 노력하고 있으며, 아래의 4가지 자료환불 조건을 꼭 확인해주시기 바랍니다.

파일오류 중복자료 저작권 없음 설명과 실제 내용 불일치
파일의 다운로드가 제대로 되지 않거나 파일형식에 맞는 프로그램으로 정상 작동하지 않는 경우 다른 자료와 70% 이상 내용이 일치하는 경우 (중복임을 확인할 수 있는 근거 필요함) 인터넷의 다른 사이트, 연구기관, 학교, 서적 등의 자료를 도용한 경우 자료의 설명과 실제 자료의 내용이 일치하지 않는 경우

이런 노하우도 있어요!더보기

찾던 자료가 아닌가요?아래 자료들 중 찾던 자료가 있는지 확인해보세요

  • 파워포인트파일 Algorithm Analysis - ACM-ICPC 소개 20페이지
    100 팀이 Stockholm 에서 벌어진 세계 결선에 출전하여 러시아의 St ... Conclusion 학생의 입장 수업시간에 배웠던 내용을 실제 문제에 적용하여 ... Algorithm : O(VlogE), V-1 번 Dijkstra 수행하면
최근 본 자료더보기
  • 프레시홍 원기회복
  • 프레시홍 원기회복
  • 프레시홍 원기회복
  • 프레시홍 원기회복
탑툰 이벤트
Dijkstra 알고리즘을 ST에 적용
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
  • 레이어 팝업
AI 챗봇
2024년 05월 23일 목요일
AI 챗봇
안녕하세요. 해피캠퍼스 AI 챗봇입니다. 무엇이 궁금하신가요?
3:32 오전
New

24시간 응대가능한
AI 챗봇이 런칭되었습니다. 닫기