Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Nov 28th, 2010  |  syntax: C  |  size: 3.81 KB  |  views: 242  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. }