Project#5 최단거리 찾기 D0 Hwp

  • Published on
    23-Jun-2015

  • View
    833

  • Download
    2

Embed Size (px)

Transcript

  • 1. project #5 D0 20093468 20113293 20093463 20093530 20113281

2. / 3. - : : , , : -5/29 5/31 4. -1. (1) ? a.(Vertex) (Node) , .b.(Edge) .c.(Degree) . 1 3 .d.(Adjacent) . 1 2 , 1 4 .e. (Undirected Graph) 5. f. (Directed graph) 2 3 1 , 1 3 4 .g. (Complete Graph) . , n n-1 . 6. 1) 1. - nn*n - - : -1 2. - 3. 7. a. - . b. - .4. ( Sort ) - a. - - b. - 8. - c. - , - . - - . - , , . - , . - 2 , . : http://blog.naver.com/s2miniwish?Redirect=Log&logNo=1586387532. (1) 1) greedy .(2) 1) S . 9. 2) w Dist[w] S w . 3) Dist[w] . 4) previous[n] vertex .(3) 10. 3. (1) 1) 2) cycle :cycle 0 ) {if( result[i][j][x-1] < result[i][k][0] + result[k][j][0] ) {if( result[i][j][x] > result[i][k][0] + result[k][j][0] ) {result[i][j][x] = result[i][k][0] + result[k][j][0];}}}else {if( result[i][j][0] > result[i][k][0] + result[k][j][0] ) {result[i][j][x] = result[i][k][x] + result[k][j][x];}}}}}}for( i = 0 ; i < n ; i++ ) {for( j = 0 ; j < n ; j++ ) {if( result[i][j][0] > result[i][j][1] ) {if( result[i][j][0] > result[i][j][2] ) {if( result[i][j][1] > result[i][j][2] ) {x = result[i][j][0];result[i][j][0] = result[i][j][2];result[i][j][2] = x;}else {x = result[i][j][0];result[i][j][0] = result[i][j][1]; 14. result[i][j][1] = result[i][j][2];result[i][j][2] = x;}}else {x = result[i][j][0];result[i][j][0] = result[i][j][1];result[i][j][1] = x;}}else {if( result[i][j][0] < result[i][j][2] ) {if( result[i][j][1] > result[i][j][2] ) {x = result[i][j][1];result[i][j][1] = result[i][j][2];result[i][j][2] = x;}}else {x = result[i][j][0];result[i][j][0] = result[i][j][2];result[i][j][2] = result[i][j][1];result[i][j][1] = x;}}}}printf(" Graph weight array :n");for (i = 0; i < n; i++) {for(j = 0; j < n; j++) {if( graph[i][j] == 30000 )printf(" oo");elseprintf("%3d", graph[i][j]);}printf("n");}printf("n");for( x = 0 ; x < 3 ; x++ ) {printf(" Shortest Path %d weight array :n",x+1);for ( i = 0 ; i < n ; i++) { 15. for( j = 0 ; j < n ; j++) {if( result[i][j][x] == 30000 ) {result[i][j][x] = result[i][j][x-1];printf("%3d", result[i][j][x]);}elseprintf("%3d", result[i][j][x]);}printf("n");}printf("n");}UnInitGraph(n);fclose(input);printf(" .....);getch();}void InitGraph(int n) {int i,j;graph = (int **)malloc(n*sizeof(int *));result = (int ***)malloc(n*sizeof(int **));max_tmp = (int ***)malloc(n*sizeof(int **));node = (char *)malloc(n*sizeof(char));for( i = 0 ; i < n ; i++ ) {graph[i] = (int *)malloc(n*sizeof(int));result[i] = (int **)malloc(n*sizeof(int *));max_tmp[i] = (int **)malloc(n*sizeof(int *));node[i] = 0;for( j = 0 ; j < n ; j++ ) {result[i][j] = (int *)malloc(3*sizeof(int));max_tmp[i][j] = (int *)malloc(2*sizeof(int));graph[i][j] = 30000;result[i][j][0] = 30000;result[i][j][1] = 30000;result[i][j][2] = 30000;max_tmp[i][j][0] = 30000;max_tmp[i][j][1] = 0;}}} 16. void UnInitGraph(int n) {int i,j;for( i = 0 ; i < n ; i++ ) {for( j = 0 ; j < n ; j++ ) {free(result[i][j]);free(max_tmp[i][j]);}free(graph[i]);free(result[i]);free(max_tmp[i]);}free(graph);free(result);free(max_tmp);free(node);} 17. - 18. - .- . 3 , .- . . .