알고리즘(3판)(FOUNDATION OF ALGORITHMS USING C++ PSEUDOCODE) 4장 연습문제

Dev
개인인증판매자스토어
최초 등록일
2016.09.15
최종 저작일
2015.05
11페이지/한글파일 한컴오피스
가격 1,500원 할인쿠폰받기
다운로드
장바구니
퀴즈풀이 출석이벤트

소개글

알고리즘(3판)(FOUNDATION OF ALGORITHMS USING C++ PSEUDOCODE) 4장 예제코드 및 연습문제
*연습문제는 2번,3번, 6번, 8번, 11번, 12번, 17번, 20번, 24번, 25번, 26번, 27번, 28번만 포함되어 있습니다. 착오 없으시길 바랍니다.

목차

없음

본문내용

8 최소비용 신장 트리에 사이클이 존재할 수 있다고 생각하는가? 그리고 왜 그런 답이 나오는지를 밝혀라

최소비용 신장 트리에서 사이클이 존재할 수 없다. 왜냐하면 최소비용 신장 트리 이전에 신장 트리 자체가 사이클이 포함돼 있지 않은 그래프이기 때문.

ㆍ11 다익스트라 알고리즘을 사용하여 문제 2의 그래프에서 정점 v4에서 다른 모든 정점으로 가는 최단경로를 구하라. 그리고 수행되는 절차를 단계별로 보여라. 여기서 각 비방향 이음선은 같은 가중치를 가진 2개의 쌍방향 이음선을 나타낸다고 가정하자.

<중략>

문제: 가중치포함 방향그래프에서 v1에서 다른 모든 정점으로 가는 최단경로를 구하라.
입력: 정수 n>=2와 정점의 개수가 n인 연결된, 가중치포함 비방향그래프. 이 그래프는 2차원 배열 W로 표현되며, 행과 열의 인덱스는 각각 1부터 n까지이다. 여기서 W[i][j]는 I번째 정점에서 j번째 정점을 잇는 이음선상의 가중치가 된디.
출력: 최단경로상에 놓여 있는 이음선의 집합 F
void dijkstra(int n, const number W[][], set of edges& F){
index I, vnear;
edge e;
index touch[2..n];
number length[2...n];

F = empty_set;
for ( i = 2; i <= n; i++){//각 정점에 대해서, v1에서 출발하는 현재 최단경로의
touch[i] = 1;//마지막 정점을 v1으로 초기화
length[i] = W[1][i];//그 경로의 길이는 v1에서의 이음선상의 가중치로 초기화
}
repeat ( n - 1 times){//n-1개 정점을 모두 Y에 추가
min = ∞;
for ( I = 2; I <= n; I++){//최단경로를 갖는지 각 정점 점검
f ( 0 <= length[i] < min ) {
min = length[i];
vnear = i;
}

참고 자료

없음

자료후기(2)

Dev
판매자 유형Gold개인인증

주의사항

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

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

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

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

우수 콘텐츠 서비스 품질인증 획득
최근 본 자료더보기
알고리즘(3판)(FOUNDATION OF ALGORITHMS USING C++ PSEUDOCODE) 4장 연습문제