Từ 1 tới 7 trên tổng số 7 kết quả

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

  1. #1
    Ngày gia nhập
    01 2008
    Bài viết
    7

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

    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:
    1. #include<conio.h>
    2. #include<stdio.h>
    3. #include<mem.h>
    4. #define MAX 20
    5. //#define FILEDL "matranke.txt"*
    6. #define vocuc 65000
    7. unsigned a[MAX][MAX],n,//ma tran ke cua do thi
    8. T[MAX],//tap dinh
    9. d[MAX],//do dai dinh s den dinh bat ky
    10. truoc[MAX],//thu tu cac dinh
    11. chuaxet[MAX],//danh dau cac dinh chua xet
    12. dau,cuoi;//dinh xuat phat va ket thuc duong di
    13. int docfile()
    14. //doc du lieu tu file
    15. //1 thanh cong ,o that bai
    16. {
    17.     FILE *f;
    18.     unsigned i,j;
    19.     f=fopen("C:\\matranke.txt","r+");
    20.     if(f==NULL)
    21.     {
    22.                printf("doc file bi loi");
    23.                return 0;
    24.     }
    25.     //bat dau doc du lieu
    26.     fscanf(f,"%u",&n);
    27.     for(i=0;i<n;i++)
    28.      for(j=0;j<n;j++)
    29.       fscanf(f,"%u",&a[i][j]);
    30.       fclose(f);
    31.     return 1;
    32.    
    33. }
    34. void xuatmatran()
    35. //in ma tran ke ra man hinh
    36. {
    37.      unsigned i,j;
    38.      for(i=0;i<n;i++)
    39.      {
    40.          for(j=0;j<n;j++)
    41.          printf("%5d",a[i][j]);
    42.          printf("\n");          
    43.      }
    44. }
    45. int timdinh()
    46. //tim dinh u chua xet co d[u] nho nhat
    47. {
    48.       int i,min=0;
    49.       while((chuaxet[min]==0||d[min]==0)&&min<n)min++;
    50.       for(i=min+1;i<n;i++)
    51.       if(chuaxet[i]&&d[i]>0&&d[i]<d[min])
    52.       min=i;
    53.       return min;
    54.      
    55. }
    56. void inketqua()
    57. //in duong di ngan nhat tim duoc
    58. {
    59.      unsigned i;
    60.      if(d[cuoi]==0)
    61.      {
    62.            printf("khong co duong di \n");
    63.            return;
    64.      }
    65.      printf("duong di ngan nhat la\n");
    66.      i=cuoi;
    67.      printf("%3u<-",cuoi+1);
    68.      while(i!=dau)
    69.      {
    70.            i=truoc[i];
    71.            printf("%3u<-",i+1);      
    72.      }
    73.      printf("\n co do dai:%u.\n",d[cuoi]);        
    74.      
    75. }
    76. void dijkstra()
    77. //tim duong di ngan nhat
    78. {
    79.       unsigned u,v;
    80.       //khoi tao
    81.       memset(chuaxet,1,sizeof(chuaxet));
    82.       for(v=0;v<n;v++)
    83.       {
    84.           d[v]=a[dau][v];
    85.           truoc[v]=dau;
    86.                  
    87.       }
    88.       d[dau]=0;
    89.       chuaxet[dau]=0;
    90.       //buoc lap
    91.       while(1)
    92.       {
    93.               u=timdinh();
    94.               if(u>=n||d[u]==0)//da xet het dinh
    95.               {
    96.                   inketqua();
    97.                   break;                  
    98.               }
    99.               chuaxet[u]=0;
    100.               for(v=0;v<n;v++)
    101.               if(chuaxet[v]&&a[u][v]>0&&(d[v]==0||d[v]>d[u]+a[u][v]))
    102.               //neu qua u ma duong tu dau toi v ngan hon
    103.               {
    104.                     d[v]=d[u]+a[u][v];
    105.                     truoc[v]=u;
    106.               }
    107.       }
    108. }
    109. main()
    110. {
    111.      
    112.       if(docfile==0)
    113.        return;
    114.        printf("ma tran ke\n");
    115.        xuatmatran();
    116.        printf("\n nhap vao dinh dau[1->%u]",n);
    117.        scanf("%u",&dau);
    118.        printf("\n nhap vao dinh cuoi[1->%u]",n);
    119.        scanf("%u",&cuoi);
    120.        dau--;
    121.        cuoi--;
    122.        dijkstra();
    123.        getch();
    124. }
    ma tran cua em nhap vao la
    1234
    5670
    8910

    3215
    Đã được chỉnh sửa lần cuối bởi lethanh : 17-04-2009 lúc 12:23 PM.
    Luôn luôn lắng nghe, luôn luôn thấu hiểu

  2. #2
    Ngày gia nhập
    01 2009
    Bài viết
    201

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

  3. #3
    Ngày gia nhập
    01 2008
    Bài viết
    7

    ko ai giúp em à
    Luôn luôn lắng nghe, luôn luôn thấu hiểu

  4. #4
    Ngày gia nhập
    03 2009
    Nơi ở
    Hà Nội
    Bài viết
    1

    File ma trận của bạn đâu,up lên luôn
    chia sẻ và học hỏi
    SWOT-->Strengths (Thế mạnh), Weaknesses (Điểm yếu), Opportunities (Cơ hội) và Threats (Nguy cơ)

  5. #5
    Ngày gia nhập
    03 2008
    Bài viết
    12

    Mặc định Bạn nên bỏ debug rồi nén project lại thành file rar rồi up lên.

    Trích dẫn Nguyên bản được gửi bởi ntien268 Xem bài viết
    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.

  6. #6
    Ngày gia nhập
    03 2008
    Nơi ở
    Hồ chí minh
    Bài viết
    134

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

    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 .......

  7. #7
    Ngày gia nhập
    08 2009
    Nơi ở
    Biên Hòa - Đồng Nai
    Bài viết
    46

    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);


Các đề tài tương tự

  1. Thuật toán Dijkstra và bài toán tìm đường đi ngắn nhất giữa các đỉnh trong đồ thị
    Gửi bởi Cloud Strife trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 19
    Bài viết cuối: 26-10-2013, 09:10 AM
  2. Thuật toán C++ Thuật toán cải tiến Dijkstra tìm tất cả đường đi ngắn nhất từ a đến b
    Gửi bởi huutho444 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 4
    Bài viết cuối: 29-11-2011, 12:01 AM
  3. Tìm đường đi ngắn nhất bằng giải thuật dijkstra trong lập trình C
    Gửi bởi minhtoan991 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 25-02-2011, 12:26 PM
  4. thuật toán dijkstra cho tìm đường đi ngắn nhất?
    Gửi bởi tuanvu_n trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 24-11-2010, 01:40 AM
  5. Tỉm đường đi ngắn nhất bằng giải thuật Dijkstra
    Gửi bởi thnam35 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 13-03-2010, 11:11 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn