thuật toán tìm đường đi ngắn nhất(dijkstra)

[shogun_vn]

em có bài sau, chẳng hiểu lỗi ở chỗ nào mà nhập giá trị nào vào nó cũng báo không có đường đi, các pác giúp em với. Thank

C Code:

Lựa chọn code | Ẩn/Hiện code

#include<conio.h>
#include<stdio.h>
#include<mem.h>
#define MAX 20
//#define FILEDL "matranke.txt"*
#define vocuc 65000
unsigned a[MAX][MAX],n,//ma tran ke cua do thi
T[MAX],//tap dinh
d[MAX],//do dai dinh s den dinh bat ky
truoc[MAX],//thu tu cac dinh
chuaxet[MAX],//danh dau cac dinh chua xet
dau,cuoi;//dinh xuat phat va ket thuc duong di
int docfile()
//doc du lieu tu file
//1 thanh cong ,o that bai
{
    FILE *f;
    unsigned i,j;
    f=fopen("C:\\matranke.txt","r+");
    if(f==NULL)
    {
               printf("doc file bi loi");
               return 0;
    }
    //bat dau doc du lieu
    fscanf(f,"%u",&n);
    for(i=0;i<n;i++)
     for(j=0;j<n;j++)
      fscanf(f,"%u",&a[i][j]);
      fclose(f);
    return 1;
   
}
void xuatmatran()
//in ma tran ke ra man hinh
{
     unsigned i,j;
     for(i=0;i<n;i++)
     {
         for(j=0;j<n;j++)
         printf("%5d",a[i][j]);
         printf("\n");          
     }
}
int timdinh()
//tim dinh u chua xet co d[u] nho nhat
{
      int i,min=0;
      while((chuaxet[min]==0||d[min]==0)&&min<n)min++;
      for(i=min+1;i<n;i++)
      if(chuaxet[i]&&d[i]>0&&d[i]<d[min])
      min=i;
      return min;
     
}
void inketqua()
//in duong di ngan nhat tim duoc
{
     unsigned i;
     if(d[cuoi]==0)
     {
           printf("khong co duong di \n");
           return;
     }
     printf("duong di ngan nhat la\n");
     i=cuoi;
     printf("%3u<-",cuoi+1);
     while(i!=dau)
     {
           i=truoc[i];
           printf("%3u<-",i+1);      
     }
     printf("\n co do dai:%u.\n",d[cuoi]);        
     
}
void dijkstra()
//tim duong di ngan nhat
{
      unsigned u,v;
      //khoi tao
      memset(chuaxet,1,sizeof(chuaxet));
      for(v=0;v<n;v++)
      {
          d[v]=a[dau][v];
          truoc[v]=dau;
                 
      }
      d[dau]=0;
      chuaxet[dau]=0;
      //buoc lap
      while(1)
      {
              u=timdinh();
              if(u>=n||d[u]==0)//da xet het dinh
              {
                  inketqua();
                  break;                  
              }
              chuaxet[u]=0;
              for(v=0;v<n;v++)
              if(chuaxet[v]&&a[u][v]>0&&(d[v]==0||d[v]>d[u]+a[u][v]))
              //neu qua u ma duong tu dau toi v ngan hon
              {
                    d[v]=d[u]+a[u][v];
                    truoc[v]=u;
              }
      }
}
main()
{
     
      if(docfile==0)
       return;
       printf("ma tran ke\n");
       xuatmatran();
       printf("\n nhap vao dinh dau[1->%u]",n);
       scanf("%u",&dau);
       printf("\n nhap vao dinh cuoi[1->%u]",n);
       scanf("%u",&cuoi);
       dau--;
       cuoi--;
       dijkstra();
       getch();
}

ma tran cua em nhap vao la
1234
5670
8910

3215

[AdminPro]

File ma trận của bạn đâu,up lên luôn

[shogun_vn]

ko ai giúp em à

[ntien268]

File ma trận của bạn đâu,up lên luôn

[dragon111989]

Trích dẫn:

Nguyên bản được gửi bởi ntien268

File ma trận của bạn đâu,up lên luôn

Bạn nên bỏ debug rồi nén project lại thành file rar rồi up lên. Anh em gian hồ lười làm cái chuyện tạo project mới, rồi copy paste lắm. Mà trong project bỏ cái file ma trận vô luôn nghen bạn.

[lethanh]

Trích dẫn:

ma tran cua em nhap vao la
1234
5670
8910

3215

Có lẽ đây là file ma trận của bạn ấy.Đây là ma trân trong số,mình chưa có học thuật toán này,nhưng mà hình như dữ liệu bị sai thì phải,vì đỉnh 1 với đỉnh 1 trọng số của nó phải là vô cùng .......

[headshot]

file ma trận chưa có đỉnh ,void docfile có fscanf(f,"%u",&n);
VD:
5
0 1 0 1 2
1 0 2 3 4
1 3 0 0 8
7 6 8 0 8
5 4 3 2 0
5: tức là 5 đỉnh ,ma trận trọng số ,chú ý đường chéo 0 0 0 0 0 (tức là đỉnh có vòng)
Bài của bạn nè ,code hoàn chỉnh dễ hiểu ,muốn bít thì khi chạy F7 và Ctrl+ F7 để xem giá trị các biến

PHP Code:

/* Vi du 1 file trongso.txt cua chuong trinh
5
0 1 0 0 7
0 0 1 4 8
0 0 0 2 4
0 0 1 0 0
0 0 0 4 0
*/
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#define vocuc 10000
int start,end,n,i,j;
int danhdau[100],trongso[100][100],chiphi[100];
int dinh[100]; //luu cac dinh da di qua
int duongdi[100]; //luu cac dinh dc chon la duong di ngan nhat,sau nay in mang nay ra
void docfile()
{
    FILE *fp;
    fp=fopen("D:\\trongso.txt","rt");
    if(fp==0)
    {
        printf("File bi loi !");
        getch();
        exit(1);
    }
    else
    {
        fscanf(fp,"%d",&n);
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                fscanf(fp,"%d",&trongso[i][j]);
    }
    fclose(fp);
}
void ghifile()
{
    FILE *fp;
    fp=fopen("D:\\ketqua.txt","wt");
    if(chiphi[start]!=vocuc)
    {
        fprintf(fp,"Duong di ngan nhat tu dinh %d --> %d la:\n\t\t",start,end);
        for(i=1;i<n;i++)
            fprintf(fp,"%d --> ",duongdi[i]);
            fprintf(fp,"%d\n",duongdi[n]);
            fprintf(fp,"\nDo dai doan duong la: %d",chiphi[start]);
     }
     else
     {
        fprintf(fp,"Khong ton tai duong di tu dinh %d --> %d \n",start,end);
     }
     fclose(fp);
}
void khoitao()
{
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(trongso[i][j]==0)
                trongso[i][j]=vocuc;
    for(i=1;i<=n;i++)
        chiphi[i]=vocuc;//khoang cach tu 1 dinh den chinh no = vo cuc (co vong),co the dat o 2 vong lap tren cung dc -> chiphi[i][j]=vocuc;
}
void dijkstra()
{
    int kt; //bien lap ,neu co chi phi nho nhat thi kt=0,neu tim dc chi phi nua thi kt=1 de tiep tuc buoc lap tim kiem
    int k;//bien dung de lap
    danhdau[end]=1;
    chiphi[end]=0;
    dinh[end]=0;
    do
    {
        kt=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if((danhdau[j]==1)&&(trongso[i][j]!=vocuc)) //neu co duong di tu dinh nay den dinh kia
                {
                    if(chiphi[j]+trongso[i][j]<chiphi[i])//so sanh chi phi dang xet tu dinh bd den dinh kt,
                    {
                        chiphi[i]=chiphi[j]+trongso[i][j];//neu nho hon vo cuc ,thi cap nhat chi phi moi
                        dinh[i]=j; //gan lai dinh dang xet
                        danhdau[i]=1;
                        kt=1;
                    }
                }
    }while(kt==1);
    if(chiphi[start]!=vocuc)
    {
        duongdi[1]=start;//duong di dau tien la dinh bat dau ,de sau nay in ra 1 -->2 hoac 2-->4
        k=1;
        while(dinh[duongdi[k]]!=0)
        {
            k++;
            duongdi[k]=dinh[duongdi[k-1]];
        }
        printf("Duong di ngan nhat tu dinh %d --> %d la:\n\t\t",start,end);
        for(i=1;i<k;i++)
            printf("%d --> ",duongdi[i]);
            printf("%d\n",duongdi[k]);
            printf("Do dai doan duong la: %d",chiphi[start]);
     }
     else
     {
        printf("Khong ton tai duong di tu dinh %d --> %d \n",start,end);
     }
}
void main()
{
clrscr();
    int chon;
    do
    {
        printf("\n\n\tChuong trinh tim duong di ngan nhat tu 1 dinh den 1 dinh khac");
        printf("\n\t\t\tThuat toan Dijkstra");
        printf("\n1: Tim duong di");
        printf("\n2: Thoat");
        printf("\nBan chon:");scanf("%d",&chon);
        switch(chon)
        {
            case 1:
            {
                docfile();
                khoitao();
                printf("\nNhap vao dinh xuat phat x=");scanf("%d",&start);
                printf("Nhap vao dinh den y=");scanf("%d",&end);
                dijkstra();
                             ghifile();
                break;
            }
        }
    }while(chon!=2);
}