Ai coi dùm mình thuật toán dijikstra sai chỗ nào zị ?
C++ Code:
  1. #include <iostream.h>
  2. #include <stdio.h>
  3. #include <conio.h>
  4. #include <process.h>
  5. #include <values.h>
  6.  
  7. typedef struct
  8. {
  9.     int d;//thay tap d[i]
  10.     int pr;//thay tap pr[i]
  11.     int flags;//=1 dinh da chon,=0 dinh chua chon
  12. }VER;
  13. VER verif[20];
  14. int M;//so dinh chua chon
  15. //int n;//tong so dinh
  16. //int Matrix[20][20];
  17. int i,j;
  18. int MAX=1000;
  19. int sd; //so dinh
  20. int MT[50][50];
  21. int dfsduyet[50];
  22. void docfile()
  23. {
  24.     FILE *fp;
  25.  
  26.     int tam;
  27.     fp=fopen("E:\\CBVIP\\DOTHI\\G5.CPP", "rb");
  28.  
  29.     if(!fp)
  30.  
  31.         cout<<"khong the mo file.\n";
  32.  
  33.  
  34.         fscanf(fp, "%d", & sd);
  35.  
  36.         printf("%d\n",sd);
  37.         for(int i=0;i<sd;i++)
  38.         {
  39.             for(int j=0;j<sd;j++)
  40.             {
  41.                 fscanf(fp,"%d",&tam);
  42.                 MT[i][j]=tam;
  43.                 printf("%d ",tam);
  44.             }
  45.             printf("\n");
  46.        }
  47.        getch();
  48.     fclose(fp);
  49. }
  50. /*void DFS(int u)
  51. {
  52.     printf("%d  ",u+1);
  53.     dfsduyet[u]=1;
  54.     for(int v=0;v<sd;v++)
  55.         {
  56.             if(dfsduyet[v]==0 && MT[u][v]>0)
  57.             {
  58.                 DFS(v);
  59.             }
  60.         }
  61. } */
  62.  
  63.  
  64.  
  65.  
  66. /*void BacCanhDinh()
  67. {
  68.     int Btam, Tbac=0;   //Tong bac
  69.  
  70.     for(int i=0;i<sd;i++)
  71.     {
  72.         Btam=0;
  73.         for(int j=0;j<sd;j++)
  74.         if(MT[i][j]==1)
  75.         {
  76.             Btam=Btam+MT[i][j];
  77.  
  78.         }
  79.         Tbac=Tbac+Btam;
  80.         printf("\nBac cua dinh  %d la %d",i+1,Btam);
  81.     }
  82.     printf("\nTong Bac La : %d",Tbac);
  83.     printf("\nSo Canh Cua Do Thi La %d",Tbac/2);
  84. } */
  85. void insolieu()
  86. {
  87.     system ("cls");
  88.     printf("\n\n\tMa Tran Ke Cap : %d\n",sd);
  89.     for(i=0;i<sd;i++)
  90.     {
  91.         printf("\n");
  92.         for(j=0;j<sd;j++)
  93.             printf("\t%d",MT[i][j]);
  94.     }
  95. }
  96. void dijikstra()
  97. {
  98.     /*for(i=0;i<n;i++)
  99.         for(j=0;j<n;j++)
  100.             if(MT[i][j]==-1)
  101.                 MT[i][j]=MAX;*/
  102.     int min,vitri;
  103.     M=sd-1;
  104.     verif[0].d=0;
  105.     verif[0].pr=0;   //dinh bat dau tu 0
  106.     verif[0].flags=1;//dinh da xet
  107.     for(int i=1;i<sd;i++)//tao cac gia tri ban dau
  108.     {
  109.         verif[i].d=MT[0][i];
  110.         verif[i].pr=0;
  111.         verif[i].flags=0;//dinh chua xet
  112.     }
  113.     while (M>0)
  114.     {
  115.         min=100;
  116.         for(int i=0;i<sd;i++)//xac dinh gia tri min cua verift[i].d
  117.             if(verif[i].flags==0 && verif[i].d<=min)//dinh chua xet
  118.             {
  119.                 min=verif[i].d;
  120.                 vitri=i;
  121.             }
  122.         verif[vitri].flags=1;//dang danh dau da xet
  123.         for(i=0;i<sd;i++)//xet cac duong moi so voi vitri
  124.             if(verif[i].d>(verif[vitri].d+MT[vitri][i]))
  125.             {
  126.                 verif[i].d=verif[vitri].d+MT[vitri][i];
  127.                 verif[i].pr=vitri;
  128.             }
  129.         M--;
  130.     }
  131. }
  132. void inKQ()
  133. {
  134.     int tam;
  135.     printf("\n\n\tTHUAT TOAN DIJIKSTRA - TIM DUONG DI NGAN NHAT\n");
  136.     for(i=1;i<sd;i++)
  137.     {
  138.         printf("\n\tDuong Di Tu 1 Den %d,",i+1);
  139.         if(verif[i].d==MAX)
  140.             printf("Do Dai = i");
  141.         else
  142.             printf("Do Dai =%d,",verif[i].d);
  143.         tam=i;
  144.         while(tam!=0)
  145.         {
  146.             printf(" %d <-",tam+1);
  147.             tam=verif[tam].pr;
  148.         }
  149.         printf(" 1 ");
  150.     }
  151. }
  152.  
  153. int main()
  154. {  
  155.     system ("cls");
  156.     docfile();
  157.    //   BacCanhDinh();
  158.     //int *a,n,*b;
  159.   //    for(int i=0;i<sd;i++)
  160.    //     dfsduyet[i]=0;
  161.     // DFS(1);
  162.     insolieu();
  163.     dijikstra();
  164.     inKQ();
  165.     getch();
  166. }