SHARE
TWEET

dijkstra by function

nguyenvanquan7826 Dec 29th, 2014 994 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <cstring>
  4.  
  5. #define INP "input.inp"
  6. #define OUT "output.out"
  7.  
  8. // read data in file input
  9. int readData(int ***G, int *n, int *a, int *b) {
  10.     FILE *fi = fopen(INP, "r");
  11.     if (fi == NULL) {
  12.         printf("file input not found!\n");
  13.         return 0;
  14.     }
  15.     printf("start read file\n");
  16.  
  17.     fscanf(fi, "%d %d %d", n, a, b);
  18.  
  19.     *G = (int **) malloc((*n) * sizeof(int));
  20.     for (int i = 0; i < *n; i++) {
  21.         (*G)[i] = (int *) malloc((*n) * sizeof(int));
  22.         for (int j = 0; j < *n; j++) {
  23.             int x;
  24.             fscanf(fi, "%d", &x);
  25.             (*G)[i][j] = x;
  26.         }
  27.     }
  28.  
  29.     fclose(fi);
  30.     printf("done read file\n");
  31.     return 1;
  32. }
  33.  
  34. // thuat toan dijkstra
  35. int dijkstra(int **G, int n, int a, int b, int P[]) {
  36.  
  37.     /* Do mang tinh tu G[0][0] nen can giam vi tri
  38.      di 1 don vi de tinh toan cho phu hop*/
  39.     a--;
  40.     b--;
  41.  
  42.     printf("start dijkstra\n");
  43.  
  44.     int* Len = (int *) malloc(n * sizeof(int));
  45.     int* S = (int *) malloc(n * sizeof(int));
  46.  
  47.     int sum = 0;            // gia tri vo cung
  48.  
  49.     // tinh gia tri vo cung (sum)
  50.     for (int i = 0; i < n; i++) {
  51.         for (int j = 0; j < n; j++) {
  52.             sum += G[i][j];
  53.         }
  54.     }
  55.  
  56.     // dat vo cung cho tat ca cap canh khong noi voi nhau
  57.     for (int i = 0; i < n; i++) {
  58.         for (int j = 0; j < n; j++) {
  59.             if (i != j && G[i][j] == 0)
  60.                 G[i][j] = sum;
  61.         }
  62.     }
  63.  
  64.     for (int i = 0; i < n; i++) {
  65.         Len[i] = sum;       // khoi tao do dai tu a toi moi dinh la vo cung
  66.         S[i] = 0;           // danh sach cac diem da xet
  67.         P[i] = a;           // dat diem bat dau cua moi diem la a
  68.     }
  69.  
  70.     Len[a] = 0;             // dat do dai tu a -> a la 0
  71.  
  72.     int i;
  73.  
  74.     // tim duong di ngan nhat tu 1 dinh den moi dinh khac thi thay bang vong for:
  75.     //for (int k = 0; k < n; k++)
  76.     while (S[b] == 0) {                 // trong khi diem cuoi chua duoc xet
  77.         for (i = 0; i < n; i++)          // tim 1 vi tri ma khong phai la vo cung
  78.             if (!S[i] && Len[i] < sum)
  79.                 break;
  80.  
  81.         // i >=n tuc la duyet het cac dinh ma khong the tim thay dinh b -> thoat
  82.         if (i >= n) {
  83.             printf("done dijkstra\n");
  84.             return 0;
  85.         }
  86.  
  87.         for (int j = 0; j < n; j++) {    // tim diem co vi tri ma do dai la min
  88.             if (!S[j] && Len[i] > Len[j])
  89.                 i = j;
  90.         }
  91.  
  92.         S[i] = 1;                       // cho i vao danh sach xet roi
  93.  
  94.         for (int j = 0; j < n; j++) {    // tinh lai do dai cua cac diem chua xet
  95.             if (!S[j] && Len[i] + G[i][j] < Len[j]) {
  96.                 Len[j] = Len[i] + G[i][j];      // thay doi len
  97.                 P[j] = i;                       // danh dau diem truoc no
  98.             }
  99.         }
  100.     }
  101.     printf("done dijkstra\n");
  102.     return Len[b];
  103. }
  104.  
  105. //  truy vet duong di
  106. void back(int a, int b, int *P, int n, char *path) {
  107.  
  108.     //char *path = (char *) malloc((n * 10) * sizeof(char));
  109.  
  110.     /* Do mang tinh tu G[0][0] nen can giam vi tri
  111.      di 1 don vi de tinh toan cho phu hop*/
  112.     a--;
  113.     b--;
  114.  
  115.     printf("start find path\n");
  116.  
  117.     int i = b;
  118.     int point[n];   // danh sach cac dinh cua duong di
  119.     int count = 0;
  120.  
  121.     /* Do ta dang tinh toan tu dinh 0 nen
  122.      muon hien thi tu dinh 1 thi can dung i + 1 de phu hop */
  123.  
  124.     point[count++] = i + 1;
  125.     while (i != a) {
  126.         i = P[i];
  127.         point[count++] = i + 1;
  128.     }
  129.  
  130.     strcpy(path, "");
  131.     char temp[10];
  132.     for (i = count - 1; i >= 0; i--) {
  133.         sprintf(temp, "%d", point[i]);
  134.         strcat(path, temp);
  135.  
  136.         if (i > 0) {
  137.             sprintf(temp, " --> ");
  138.             strcat(path, temp);
  139.         }
  140.     }
  141.  
  142.     printf("done find path\n");
  143. }
  144.  
  145. void outResult(int len, char* path) {
  146.     FILE *fo = fopen(OUT, "w");
  147.  
  148.     if (len > 0) {
  149.         fprintf(fo, "\nLength of %c to %c is %d\n", path[0],
  150.                 path[strlen(path) - 1], len);
  151.     }
  152.  
  153.     fprintf(fo, "path: %s\n", path);
  154.  
  155.     fclose(fo);
  156. }
  157.  
  158. int main() {
  159.     int **G, n, a, b, len;
  160.  
  161.     if (readData(&G, &n, &a, &b) == 0) {
  162.         return 0;
  163.     }
  164.  
  165.     char *path = (char *) malloc((10 * n) * sizeof(char));
  166.     int P[n];
  167.  
  168.     len = dijkstra(G, n, a, b, P);
  169.  
  170.     if (len > 0) {
  171.         back(a, b, P, n, path);
  172.         outResult(len, path);
  173.     } else {
  174.         char *path = (char *) malloc((n * 10) * sizeof(char));
  175.         sprintf(path, "khong co duong di tu %d den %d\n", a, b);
  176.         outResult(len, path);
  177.     }
  178.  
  179.     printf("done - open file output to see result\n");
  180.     return 0;
  181. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top