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

소개글

알고리즘(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;
}

참고 자료

없음