SHARE
TWEET

dijkstra only main

nguyenvanquan7826 Dec 29th, 2014 804 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define INP "input.inp"
  4. #define OUT "output.out"
  5.  
  6. int main() {
  7.     FILE *fi = fopen(INP, "r");
  8.     FILE *fo = fopen(OUT, "w");
  9.     int n, a, b, i, sum = 0;
  10.  
  11.     // nhap du lieu tu file input
  12.     fscanf(fi, "%d%d%d", &n, &a, &b);
  13.     int G[n][n];
  14.     int S[n], Len[n], P[n];
  15.  
  16.     // nhap ma tran va tinh gia tri vo cung (sum)
  17.     for (i = 0; i < n; i++)
  18.         for (int j = 0; j < n; j++) {
  19.             fscanf(fi, "%d", &G[i][j]);
  20.             sum += G[i][j];
  21.         }
  22.     // dat vo cung cho tat ca cap canh khong noi voi nhau
  23.     for (int i = 0; i < n; i++) {
  24.         for (int j = 0; j < n; j++) {
  25.             if (i != j && G[i][j] == 0)
  26.                 G[i][j] = sum;
  27.         }
  28.     }
  29.  
  30.     /* Do mang tinh tu G[0][0] nen can giam vi tri
  31.      di 1 don vi de tinh toan cho phu hop*/
  32.     a--;
  33.     b--;
  34.  
  35.     for (int i = 0; i < n; i++) {
  36.         Len[i] = sum;                   // khoi tao do dai tu a toi moi dinh la vo cung
  37.         S[i] = 0;                       // danh sach cac diem da xet
  38.         P[i] = a;                       // dat diem bat dau cua moi diem la a
  39.     }
  40.  
  41.     Len[a] = 0;                         // dat do dai tu a -> a la 0
  42.  
  43.     // tim duong di ngan nhat tu 1 dinh den moi dinh khac thi thay bang vong for:
  44.     //for (int k = 0; k < n; k++)
  45.     while (S[b] == 0) {                 // trong khi diem cuoi chua duoc xet
  46.         for (i = 0; i < n; i++)          // tim 1 vi tri ma khong phai la vo cung
  47.             if (!S[i] && Len[i] < sum)
  48.                 break;
  49.  
  50.         // i >=n tuc la duyet het cac dinh ma khong the tim thay dinh b -> thoat
  51.         if (i >= n) {
  52.             printf("done dijkstra\n");
  53.             break;
  54.         }
  55.  
  56.         for (int j = 0; j < n; j++) {    // tim diem co vi tri ma do dai la min
  57.             if (!S[j] && Len[i] > Len[j]) {
  58.                 i = j;
  59.             }
  60.         }
  61.  
  62.         S[i] = 1;                       // cho i vao danh sach xet roi
  63.  
  64.         for (int j = 0; j < n; j++) {    // tinh lai do dai cua cac diem chua xet
  65.             if (!S[j] && Len[i] + G[i][j] < Len[j]) {
  66.                 Len[j] = Len[i] + G[i][j];      // thay doi len
  67.                 P[j] = i;                       // danh dau diem truoc no
  68.             }
  69.         }
  70.     }
  71.  
  72.     printf("done dijkstra\n");
  73.  
  74.     /* Do ta dang tinh toan tu dinh 0 nen
  75.      muon hien thi tu dinh 1 thi can dung i + 1 de phu hop */
  76.  
  77.     printf("start find path\n");
  78.  
  79.     if (Len[b] > 0 && Len[b] < sum) {
  80.         fprintf(fo, "Length of %d to %d is %d\n", a + 1, b + 1, Len[b]);
  81.  
  82.         // truy vet
  83.         while (i != a) {
  84.             fprintf(fo, "%d <-- ", i + 1);
  85.             i = P[i];
  86.         }
  87.         fprintf(fo, "%d", a + 1);
  88.     } else {
  89.         fprintf(fo, "khong co duong di tu %d den %d\n", a + 1, b + 1);
  90.     }
  91.  
  92.     printf("done find path\n");
  93.  
  94.     fclose(fi);
  95.     fclose(fo);
  96.  
  97.     printf("done - open file output to see result\n");
  98.     return 0;
  99. }
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