연습 문제

연습 문제

 아래 그래프에서 Dijkstra의 single source all destination 알고리즘을 이용하여 vertex E에서 나머지 vertex로의 최 단 경로를 구하고자 한다. 최단 경로가 발견되는 vertex의 순서는 무엇인가?

F A

B D

C E

3 5

7

2 2

5 2

2

4.2 All Pairs Shortest Paths

 문제 정의

 그래프 G에 포함된 모든 vertex의 쌍들에 대해 최단 경 로를 발견

 해법

1. V(G)에 속하는 각각의 vertex에 대해 shortestpath() 알 고리즘을 수행: 복잡도 = O(n³)

2. 동적 프로그래밍 방법(Dynamic programming

method) : 복잡도 = O(n³) with smaller constant factor

동적 프로그래밍 알고리즘

 가정: 0에서 n – 1까지 n 개의 vertex가 존재

 기본적인 자료구조

 A^k[i][j]: k보다 크지 않은 vertex들로 구성된 i에서 j까 지 최단 경로의 길이

 i에서 j까지의 최단 경로의 길이 = A^n-1

[i][j]



A

[i][j] = cost[i][j]

 연속적으로 A⁰, A¹, A², ..., A^n-1 을 생성

 A^k-1을 이용하여 A^k를 생성하는 방법

 vertex k를 지나지 않는 경로: A^k[i][j] = A^k-1[i][j]

 vertex k를 지나는 경로:



A

[i][j] = min{A

[i][j], A

[i][k] + A

[k][j]}, k≥0

A

[i][j] = cost[i][j]

Program 6.12: allcosts()

void allcosts (int cost[ ][MAX_V], int distance[][MAX_V], int n) {

/* 각 vertex에서 나머지 모든 vertex까지의 최단 경로를 계산.

cost[][]: 인접 행렬, distance[][]: 경로의 거리를 저장 */

int i, j, k;

for (i = 0; i < n; i++)

for (j = 0; j < n; j++)

distance[i][j] = cost[i][j];

for (k = 0; k < n; k++)

for (i = 0; i < n; i++)

for (j = 0; j < n; j++)

if (distance[i][k] + distance[k][j] < distance[i][j])

distance[i][j] = distance[i][k] + distance[k][j];

그림 6.34: allcosts()에서 생성되는 A ^k

A^-1 0 1 2

0 0 4 11

1 6 0 2

2 3 ∞ 0

A⁰ 0 1 2

0 0 4 11

1 6 0 2

2 3 7 0

A¹ 0 1 2

0 0 4 6

1 6 0 2

2 3 7 0

A² 0 1 2

0 0 4 6

1 5 0 2

2 3 7 0

V₀ V₁

V₂

6

4 11 2 3

이행적 폐쇄(Transitive Closure)

 Transitive Closure Matrix: A⁺

 A⁺[i][j] = 1 if there is a path of length > 0 from i to j

 Otherwise, A⁺[i][j] = 0.

 Reflexive Transitive Closure Matrix: A^*

 A^*[i][j] = 1 if there is a path of length ≥ 0 from i to j

 Otherwise, A^*[i][j] = 0.

 Program: allcosts() 알고리즘을 수정

distance[i][j] = distance[i][j] || distance[i][k] &&

distance[k][j]

Transitive Closure의 예

0 1 2 3 4

0 0 1 0 0 0 1 0 0 1 0 0 2 0 0 0 1 0 3 0 0 0 0 1 4 0 0 1 0 0

0 0 1 1 1 1 1 0 0 1 1 1 2 0 0 1 1 1 3 0 0 1 1 1 4 0 0 1 1 1

0 1 1 1 1 1 1 0 1 1 1 1 2 0 0 1 1 1 3 0 0 1 1 1 4 0 0 1 1 1

Digraph G Adjacent matrix A for G

A

A

연습 문제

 동적 프로그래밍을 이용하여 오른쪽 그래프에 대해 "All pairs shortest path"를 구하고자 한다. 아래 A⁰ 행렬을 채 우시오.

1

2 0

3

2 1

4 5 2 6

3

2

0 1 2 3

0 1 2 3

5. 작업 네트워크(Activity Networks)

 작업(Activity)

 부분 프로젝트 (divide and conquer)

 각각의 작업들이 완료되어야 전체 프로젝트가 성공적 으로 완료

 두 가지 종류의 네트워크

 Activity on Vertex (AOV) Networks

 Activity on Edge (AOE) Networks

5.1 AOV Network

 몇 가지 정의들:

 AOV Network: Digraph G (vertex = 작업, edge = 작업 들 간의 선행 관계)

 u에서 v까지 방향 경로(directed path)가 존재할 경우

 u = predecessor of v, v = successor of u



Immediate Predecessor (Successor): <u, v>



Partial Order: transitive



Topological Order: vertex들 간의 선행 관계를 고려하

 Topological Sort

작업들 간에는 partial order만 존재할 수 있으므로,

AOV Network의 예

과목번호 과목명 선수과목

C1 C언어 None

C2 이산수학 None

C3 자료구조 C1, C2

C4 미분적분 I None

C5 미분적분 II C4

C6 선형대수 C5

C7 알고리즘 분석 C3, C6

C8 어셈블리어 C3

C9 운영체제 C7, C8

C10 프로그래밍언어 C7

C11 컴파일러 설계 C10

C12 인공 지능 C7

C13 계산 이론 C7

C14 병렬 알고리즘 C13

C15 수치 해석 C5

C1

C2

C4

C3

C8

C7

C5 C6

C9

C10

C12

C11

C13 C14

C15

(a) Courses needed for a computer science degree

(b) AOV network representing courses as vertices and edges as prerequisites

Program 6.13: Topological Sort

for ( i = 0; i < n; i++) {

if (every vertex has a predecessor) {

fprintf (stderr, "Network has a cycle.\ n");

exit (1);

}

pick a vertex v that has no predecessors;

output v;

delete v and all edges leading out of v from the network;

}

그림 6.39: Topological Sort의 동작

V₁ V₂ V₃

V₀ V₄

V₅

(a) initial

V₁ V₂ V₃

V₄ V₅

(b) V₀

V₁

V₂ V₄ V₅

(c) V₃

V₁

V₄ V₅

(d) V₂

V₁

V₄

(e) V₅

V₄

(f) V₁ (g) V₄

생성된 topological order : V , V , V , V , V , V