Guest User

Untitled

a guest
Nov 28th, 2010
613
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* CHUONG TRINH MO TA THUAT TOAN DIJSTRA TIM DUONG DI NGAN NHAT TRONG DO THI.
  2.  * code by YoYoLove From FAMILUG - Girlxitin.com
  3.  * file dau vao: in.txt phai tao cung folder chua source, chua ma tran khoang cach
  4.  * gia tri vo cung duoc gan bang 999
  5.  * vi du:
  6. 0 1 2 3 999 999 999 999
  7. 1 0 1 999 5 999 999 999
  8. 2 1 0 1 999 1 999 999
  9. 3 999 1 0 999 999 2 999
  10. 999 5 999 999 0 2 999 1
  11. 999 999 1 999 2 0 1 3
  12. 999 999 999 2 999 1 0 1
  13. 999 999 999 999 1 3 1 0
  14. */
  15. #include <stdio.h>
  16. #define  MAX 8 //so dinh cua ma traN
  17.  
  18. const INFINITE=999; // gia tri thay the cho gia tri vo cung
  19. int matrix[MAX][MAX]; //tao ma tran khoang cach
  20. int a=0, b=0, num=0; //tao bien toan cuc
  21.  
  22. int allselected(int *selected)
  23. {
  24.     int i;
  25.     for(i=0;i<MAX;i++)
  26.         if(selected[i]==0)
  27.             return 0;
  28.     return 1;
  29. }
  30.  
  31. void dijstra(int matrix[][MAX],int *preced,int *distance) //ham dijstra
  32. {
  33.     int selected[MAX]={0};
  34.     int current=0,i,k,dc,smalldist,newdist;
  35.    
  36.     for(i=0;i<MAX;i++)
  37.     {
  38.         distance[i]=INFINITE; // gan g.tri vo cung
  39.     }
  40.    
  41.     selected[current]=1; //chon dinh dau la 1
  42.     distance[0]=0; // khoang cac tu dinh 1->1 la 0
  43.     current=0; //gan nhan 0 cho dinh 1
  44.     while(!allselected(selected))
  45.     {
  46.         smalldist=INFINITE; //khoang cach nho nhat
  47.         dc=distance[current];
  48.         for(i=0;i<MAX;i++) //bat dau thuat toan dijstra
  49.         {
  50.             if(selected[i]==0)
  51.             {
  52.                    newdist=dc+matrix[current][i]; //khoang cach moi
  53.                     if(newdist<distance[i])
  54.                         {
  55.                             distance[i]=newdist;
  56.                             preced[i]=current;
  57.                         }
  58.                     if(distance[i]<smalldist)
  59.                         {
  60.                             smalldist=distance[i];
  61.                             k=i;
  62.                         }
  63.             }
  64.         } //ket thuc thuat toan dijstra
  65.         current=k;
  66.         selected[current]=1;
  67.    }
  68. }
  69.  
  70. void creat_distmatrix() //ham tao ma tran khoang cach
  71. {
  72.     printf("\n Nhap ma tran khoang cach");
  73.     for(a=0;a<MAX;a++)
  74.     {
  75.         printf("\n hang i = %d: ",a+1);
  76.         for(b=0;b<MAX;b++)
  77.         {
  78.         printf("\n gia tri cua hang %d cot %d: ",a+1,b+1);
  79.         scanf("%d", &num);
  80.         matrix[a][b]=num;
  81.         }
  82.     }
  83. }
  84.  
  85. int main()
  86. {
  87.     int choose;
  88.     FILE *of, *inf; //tao con tro tep
  89.  
  90.     printf("\n Lua chon cach nhap du lieu...................................... ");
  91.     printf("\n Nhap tu ban phim chon 0 - nhap tu file chon 1, xong an Enter :..");
  92.     scanf("%d", &choose);
  93.    
  94.     if(choose==0)
  95.     {
  96.         creat_distmatrix();
  97.     }
  98.    
  99.     if(choose==1)
  100.     {
  101.         of=fopen("in.txt","r");  //mo tep in.txt de doc thong tin
  102.         if(of==NULL)       // neu tep khong ton tai
  103.         {
  104.             printf("\n Qua tirnh nhap du lieu loi do tap tin khong ton tai... Enter de ket thuc");
  105.         }
  106.         else //neu tep ton tai
  107.         {
  108.             for(a=0;a<MAX;a++)
  109.             {
  110.                 for(b=0;b<MAX;b++)
  111.                 {
  112.                     fscanf(of,"%d", &num); //gan cac phan tu trong tep vao "num"
  113.                     matrix[a][b]=num; // Ghi tri cua "num" vao ma tran
  114.                 }
  115.             }
  116.         }
  117.     }
  118.    
  119.     if(of!=NULL) //neu tep ton tai
  120.     {
  121.         //hien thi ma tran
  122.         printf("\n Ma tran da nhap: \n");
  123.         for(a=0;a<MAX;a++)
  124.         {
  125.             for(b=0;b<MAX;b++)
  126.             {
  127.                 printf(" %3d", matrix[a][b]);
  128.             }
  129.             printf("\n");
  130.         }
  131.        
  132.         //tinh toan ket qua cua thuat toan
  133.         int i,preced[MAX]={0},distance[MAX];
  134.         dijstra(matrix,preced,distance);
  135.        
  136.         //in ket qua tren man hinh
  137.         printf("\n Thu tu gan nhan cho cac dinh: ");
  138.         for(i=0;i<MAX;i++)
  139.         {
  140.             printf("\n Dinh %d: ",i+1);
  141.             printf("%d\n",distance[i]);
  142.         }
  143.         printf("\n Nhan cua dinh cuoi: %d", distance[MAX-1]);
  144.        
  145.         //in ra file out.txt
  146.         inf=fopen("out.txt","w");
  147.         fprintf(inf,"\n Thu tu gan nhan cho cac dinh: ");
  148.         for(i=0;i<MAX;i++)
  149.         {
  150.             fprintf(inf,"\n Dinh %d: ",i+1);
  151.            fprintf(inf,"%d\n",distance[i]);
  152.         }
  153.         fprintf(inf,"\n Nhan cua dinh cuoi: %d", distance[MAX-1]);
  154.         fclose(of);
  155.         fclose(inf);
  156.     }
  157.  
  158.     return 0;
  159. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×