DP 기반 최단경로 – 자료 구조 및 전략 (1/4) 주어진 그래프에 대한 W:인접행렬(adjacent matrix) 표현 W

Presentation on theme: "DP 기반 최단경로 – 자료 구조 및 전략 (1/4) 주어진 그래프에 대한 W:인접행렬(adjacent matrix) 표현 W"— Presentation transcript:

1 DP 기반 최단경로 – 자료 구조 및 전략 (1/4) 주어진 그래프에 대한 W:인접행렬(adjacent matrix) 표현 W
v5 v1 v4 v2 v3 3 5 1 9 2 4 W

2 DP 기반 최단경로 – 자료 구조 및 전략 (2/4) 주어진 그래프에 대한 최단경로의 길이를 나타내는 행렬: D 즉,
알고리즘에 의해서 생성할 목표에 해당하는 자료구조 즉, W: 주어진 그래프의 인접행렬 표현 D: 주어진 그래프의 각 정점들 사이의 최단경로의 길이 v5 v1 v4 v2 v3 3 5 1 9 2 4 D

3 DP 기반 최단경로 – 자료 구조 및 전략 (3/4)

4 DP 기반 최단경로 – 자료 구조 및 전략 (4/4) v5 v1 v4 v2 v3 3 5 1 9 2 4 예제

5 DP 기반 최단경로 – 설계 (1/4) v5 v1 v4 v2 v3 3 5 1 9 2 4

6 DP 기반 최단경로 – 설계 (2/4) v5 v1 v4 v2 v3 3 5 1 9 2 4

7 DP 기반 최단경로 – 설계 (3/4) 1. D(k-1)을 가지고 D(k)를 계산하는 재귀적 속성(recursive property)을 정립 경우 2에 대한 그림설명 2. 상향식으로 k = 1부터 n까지 다음과 같이 상기 과정을 반복하여 해를 구한다. D(0), D(1),……., D(n) {v1, v2,…, vk-1} {v1, v2,…, vk-1}

8 DP 기반 최단경로 – 설계 (4/4) v5 v1 v4 v2 v3 3 5 1 9 2 4 예제 W

9 DP 기반 최단경로 – Floyd 알고리즘 1 (1/2)
문제: 가중치 포함 방향 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계산하라. 입력: 가중치 포함 방향 그래프 W, 그래프에서의 정점의 수 n 출력: 최단거리의 길이가 포함된 배열 D 알고리즘 void floyd(int n, number[][] W, number[][] D){ index i, j, k; D = W; for(k=1; k <= n; k++) for(i=1; i <= n; i++) for(j=1; j <= n; j++) D[i][j] = minimum(D[i][j], D[i][k]+D[k][j]); }

10 DP 기반 최단경로 – Floyd 알고리즘 1 (2/2)
모든 경우를 고려한 분석: 단위연산: for-j 루프안의 할당문 입력크기: 그래프에서의 정점의 수 n

11 DP 기반 최단경로 – Floyd 알고리즘 2 (1/4)
문제: 가중치 포함 방향 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계산하고, 각각의 최단경로를 구하라. 입력: 가중치 포함 방향 그래프 W, 그래프에서의 정점의 수 n 출력: 최단경로의 길이가 포함된 배열 D, 다음을 만족하는 배열 P vi 에서 vj 까지 가는 최단경로의 중간에 놓여 있는 정점이 존재하는 경우  그 놓여 있는 정점 중에서 가장 큰 인덱스 vi 에서 vj 까지 가는 최단경로의 중간에 놓여 있는 정점이 없는 경우  0

12 DP 기반 최단경로 – Floyd 알고리즘 2 (2/4)
void floyd2(int n, number W[][], number D[][], index P[][]){ index i, j, k; for(i=1; i <= n; i++) for(j=1; j <= n; j++) P[i][j] = 0; D = W; for(k=1; k<= n; k++) for(j=1; j<=n; j++) if ((D[i][k] + D[k][j]) < D[i][j]) { P[i][j] = k; D[i][j] = D[i][k] + D[k][j]; } vi에서 vj로 가는데 vk를 지난다는 정보를 저장 D[i][j] = minimum(D[i][j], D[i][k]+D[k][j]);

13 DP 기반 최단경로 – Floyd 알고리즘 2 (3/4)
v5 v1 v4 v2 v3 3 5 1 9 2 4 예 1) v2 에서 v1 까지 가는 최단경로 P[2][1]=5, P[2][5]=4, P[2][4]=0 그러므로, v2  v4  v5  v1 예 2) v5 에서 v3 까지 가는 최단경로 P[5][3]=4, P[5][4]=1, P[5][1]=0 그러므로, v5  v1  v4  v3

14 DP 기반 최단경로 – Floyd 알고리즘 2 (4/4)
void path(index q, r){ if (P[q][r] != 0) { path(q, P[q][r]); System.out.print(“ v“ + P[q][r]); } 최단경로 출력 알고리즘 (주의: 교재와 상이) 앞서의 행렬 P로 path(5,3)을 호출하면 다음과 같이 수행된다. path(5, 3) path(5, P[5][3]=4) path(5, P[5][4]=1) P[5][1]=0  return; v1 v4 결과: v1 v4. (즉, v5에서 v3으로 가는 최단경로는 v5, v1, v4, v3,이다.)

15 [실습 6] Floyd 알고리즘 작성 Floyd 알고리즘을 Java 로 코딩하기 Floyd.java 를 분석하기
“// Write Codes...” 라고 되어진 세 부분을 채워넣기 다음과 같이 출력되어야 함