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

Đề tài: Tỉm đường đi ngắn nhất bằng giải thuật Dijkstra

  1. #1
    Ngày gia nhập
    06 2007
    Bài viết
    4

    Mặc định Tỉm đường đi ngắn nhất bằng giải thuật Dijkstra

    Các bạn ơi, có ai viết được code Tỉm đường đi ngắn nhất bằng giải thuật Dijkstra bằng ngôn ngữ C không? Mình mới học Turbo C (trước đây cũng không có học Pascal và cũng chưa biết gì về C++). Mình search trên mạng thấy mấy bài toán như vậy nhưng toàn viết bằng C++ hoặc Pascal nên không hiểu gì hết?Có bạn nào giúp mình với. Thanks nhiều!

  2. #2
    Ngày gia nhập
    10 2008
    Bài viết
    171

    Bài này trên tài liệu có rất nhiều nhưng chủ yếu viết bằng pascal bạn tự tìm đọc nhé.
    C Code:
    1. void dijkstra(int a[][10],int n)
    2. {int truoc[10],d[10],b[10],s,t,i,u,min;
    3.  printf("\nNhap diem bat dau s= ");
    4.  scanf("%d",&s);
    5.  printf("\nNhap diem ket thuc t= ");
    6.  scanf("%d",&t);
    7.  for(i=1;i<=n;i++)
    8.  {d[i]=a[s][i];
    9.   truoc[i]=s;
    10.   b[i]=1;
    11.  }
    12.  truoc[s]=0;
    13.  d[s]=0;
    14.  b[s]=0;
    15.  while(b[t])
    16.  {min=vc;
    17.   for(i=1;i<=n;i++)
    18.   if(b[i]&&min>d[i])
    19.   {min=d[i];
    20.    u=i;
    21.   }
    22.   b[u]=0;
    23.   if(b[t])
    24.   {for(i=1;i<=n;i++)
    25.    {if((b[i])&&(d[u]+a[u][i]<d[i]))
    26.     {d[i]=d[u]+a[u][i];
    27.      truoc[i]=u;
    28.     }
    29.    }
    30.   }
    31.  }
    32.  printf("%d",t);
    33.  i=truoc[t];
    34.  while(i!=s)
    35.  {printf("%2d",i);
    36.   i=truoc[i];
    37.  }
    38.  printf("%2d",s);
    39.  printf("\n%d",d[t]);
    40. }
    Code này còn thiếu hàm main và biến bạn tự thêm vào hoàn chỉnh nhé.
    Đã được chỉnh sửa lần cuối bởi QuangHoang : 03-12-2009 lúc 12:04 PM.

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

    bạn tham khảo cái này coi!
    PHP Code:
    #include<conio.h>
     #include<stdio.h>
     #define vc 32767
     
    int x,y,n,chuaxet[50],c[30][30],T[20],s[30];
     
    void nhapmt();
     
    void khoitao();
     
    void xuatmt();
     
    void timduong();
     
    main()
     { do{ 
    printf("\n nhap n=");
             
    scanf("%d",&n);                                                                                             
          } while(
    n<0||n>30);
        
    nhapmt();
        
    xuatmt();
        
    khoitao();
        
    printf("\n nhap vao dinh xuat phat x=");
        
    scanf("%d",&x);
        
    printf("\n nhap vao dinh den y=");
        
    scanf("%d",&y);
        
    timduong();
        
    getch();
     }
     
    void nhapmt()
     { 
    int i,j;
        for(
    i=1;i<=n;i++)
          for(
    j=1;j<=n;j++)
             {
    printf("c[%d][%d]=",i,j);
              
    scanf("%d",&c[i][j]);
              }
     }
     
    void xuatmt()
     {for(
    int i=1;i<=n;i++)
         { for(
    int j=1;j<=n;j++) printf("%2d",c[i][j]);
            
    printf("\n");
         }
     }
     
    void khoitao()
     { 
    int i,j;
        for(
    i=1;i<=n;i++)
          for(
    j=1;j<=n;j++) if(c[i][j]==0c[i][j]=vc;
        for(
    i=1;i<=n;i++) s[i]=vc;
     }
     
    void timduong()
     { 
    int kt,k,b[20];
        
    int i,j;
        
    chuaxet[y]=1;s[y]=0;T[y]=0;
        do { 
    kt=0;
             for(
    i=1;i<=n;i++)
             for(
    j=1;j<=n;j++) if((chuaxet[j]==1)&&(c[i][j]!=vc))
                                  {    if(
    s[j]+c[i][j]<s[i])
                                          { 
    s[i]=s[j]+c[i][j];
                                             
    T[i]=j;
                                             
    chuaxet[i]=1;
                                            
    kt=1;
                                          }
                                  }
            }while(
    kt==1);
        if(
    s[x]!=vc)
         {
            
    b[1]=x;k=1;
            while(
    T[b[k]]!=0)
                {
                
    k++;
                
    b[k]=T[b[k-1]];
                }
              
    printf("\tDuong di ngan nhat tu dinh %d --> %d la:\n\t\t",x,y);
            for(
    i=1;i<k;i++)
                
    printf("%d -->",b[i]);
            
    printf("%d\n",b[k]);
            
    printf("\t\tDo dai doan duong la:%d",s[x]);
         }
         else
            {
            
    printf("\tKhong ton tai duong di tu dinh %d --> %d \n",x,y);
            }
     } 

  4. #4
    Ngày gia nhập
    06 2007
    Bài viết
    4

    cám ơn các bạn nhiều lắm

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

    cho mình hỏi
    C Code:
    1. void timduong()
    2.  { int kt,k,b[20];
    3.     int i,j;
    4.     chuaxet[y]=1;s[y]=0;T[y]=0;
    5.     do { kt=0;
    6.          for(i=1;i<=n;i++)
    7.          for(j=1;j<=n;j++) if((chuaxet[j]==1)&&(c[i][j]!=vc))
    8.                               {    if(s[j]+c[i][j]<s[i])
    9.                                       { s[i]=s[j]+c[i][j];
    10.                                          T[i]=j;
    11.                                          chuaxet[i]=1;
    12.                                         kt=1;
    13.                                       }
    14.                               }
    15.         }while(kt==1);
    16.     if(s[x]!=vc)
    17.      {
    18.         b[1]=x;k=1;
    19.         while(T[b[k]]!=0)
    20.             {
    21.             k++;
    22.             b[k]=T[b[k-1]];
    23.             }
    24.           printf("\tDuong di ngan nhat tu dinh %d --> %d la:\n\t\t",x,y);
    25.         for(i=1;i<k;i++)
    26.             printf("%d -->",b[i]);
    27.         printf("%d\n",b[k]);
    28.         printf("\t\tDo dai doan duong la:%d",s[x]);
    29.      }
    30.      else
    31.         {
    32.         printf("\tKhong ton tai duong di tu dinh %d --> %d \n",x,y);
    33.         }
    34.  }



    ở phần b[20]
    C Code:
    1. while( T[b[k]] != 0 )
    2.             {
    3.                 k++;
    4.                 b[k] = T[b[k-1]];
    5. }
    có ý nghĩa ra sao?
    printf("\t\tDo dai doan duong la: %d",s[x]); thì s[x] sẽ in gia trị tìm được ở chổ nào?
    cám ơn các bạn nhiều lắm

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

  1. Đường đi ngắn nhất-Giải thuật dijkstra.Nhờ các pro xem giai thich e hieu voi
    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: 08-04-2011, 06:18 PM
  2. Đường đi ngắn nhất = giải thuật dijkstra trong Dev C,xem & sửa giúp em với..outtime
    Gửi bởi minhtoan991 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 1
    Bài viết cuối: 01-04-2011, 06:12 PM
  3. Lập trình C Tìm đường đi ngắn nhất viết bằng giải thuật Dijkstra trong lập trình C
    Gửi bởi minhtoan991 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 9
    Bài viết cuối: 25-03-2011, 11:35 AM
  4. 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
  5. thuật toán tìm đường đi ngắn nhất(dijkstra)
    Gửi bởi shogun_vn trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 22-11-2010, 12:45 AM

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