Trang 1 trên tổng số 3 123 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 23 kết quả

Đề tài: 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ị

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

    Question 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ị

    Xin hướng cách cài đặt thuật toán dijkstra thực hiện việc tìm đi ngắn nhất giữa 2 đỉnh bất kì trong đồ thị.

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

    Yêu cầu của bạn được giải quyết rồi đây:
    C++ Code:
    1. #include "iostream"
    2. #include "fstream"
    3. #include "iomanip"
    4. using namespace std;
    5. int n;
    6. int aMTK[20][20];//do thi
    7. int s[10];/*mang dung de danh dau co dinh truoc cua cac dinh,cái này ko quan trong lắm có thể ko dùng cũng được*/
    8. int truoc[10];//luu cac dinh truoc tai thoi diem dang xet cua dinh
    9. int mark[10];//de danh dau dinh dang xet
    10. int dodai[10];//luu do dai  duong di tu dinh bat dau den cac dinh con lai
    11. int count=0;//de dich cac dinh
    12.  
    13.  
    14. void read(char *filename)//doc file tu mot matra(do thi)cho truoc
    15. {
    16.     fstream FileMTK;
    17.     //sMTK.n=0;
    18.     FileMTK.open(filename,ios::in);
    19.     if (FileMTK.bad())
    20.     {
    21.         cout<<"Error";
    22.         return ;
    23.     }
    24.     FileMTK>>n;
    25.     if(!n)
    26.     {
    27.         cout<<"Empty Matrix !"<<endl;
    28.         return ;
    29.     }
    30.     for (int i=1; i<=n; i++)
    31.         for (int j=1; j<=n; j++)
    32.             {
    33.             FileMTK>>aMTK[i][j];
    34.             //if(!(sMTK.aMTK[i][j]))
    35.             //  return 0;
    36.             }
    37.     FileMTK.close();
    38.  
    39. }
    40. void printffile()//in file
    41. {
    42.     cout<<" Ma tran ke lay tu file la: "<<endl;
    43.     cout<<n<<endl;
    44.     for (int i=1; i<=n; i++)
    45.     {
    46.         for (int j=1; j<=n;j++)
    47.             cout<<aMTK[i][j]<<" ";
    48.         cout<<endl;
    49.     }
    50. }
    51. void initdijksytra()//khoi tao cac mang
    52. {
    53.     for(int i=1;i<=n;i++)
    54.     {
    55.         dodai[i]=1000;//khoi tao do dai tu dinh dang xet den cac dinh con la 999
    56.         mark[i]=0;//khoi tao cac dinh chua xet la 0;
    57.         truoc[i]=0;//khoi tao dinh truoc cua cac dinh hien tai la 0;
    58.         s[i]=0;//luu dinh truoc cua cac dinh ma co duong di nho nhat,khoi tao la 0;
    59.     }
    60.    
    61. }
    62. int minimum()//tim dinh co khoang cach den dinh dang xet ngan nhat
    63. {  
    64.      int min=1000;
    65.      int i,t;
    66.      for(i=1;i<=n;i++)
    67.      {
    68.           if(mark[i]!=1)//neu chua xet dinh i;
    69.           {
    70.               if(min>=dodai[i])//neu dodai[i] nho hon min
    71.               {
    72.                    min=dodai[i];//min bang do dai cua dodai[i]
    73.                    t=i;//t bang dinh i
    74.               }
    75.         }
    76.      }
    77.      return t;
    78.  
    79. }
    80. void induongdi(int s,int j,int truoc[])
    81. {
    82.   cout<<"\n";
    83.     if(j==s)
    84.     {
    85.         printf("%d",s);
    86.     }
    87.     else
    88.         if(truoc[j]==0)
    89.             printf("khong co duong di tu dinh %d den dinh %d\n",s,j);
    90.         else
    91.         {
    92.             induongdi(s,truoc[j],truoc);//de quy de in duong di tu dinh bat dau den j
    93.             printf("..%d",j);
    94.         }
    95. }
    96. void dijkstra(int source)//diem bat dau
    97. {
    98.   int i,j,u;
    99.   while(count<n)//lan luot xet cac dinh
    100.   {
    101.      u=minimum(); //tim dinh co duong di ngan nhat tu dinh dang xet
    102.      s[++count]=u;//danh dau  dinh ke u có dinh truoc la u
    103.      //bat dau lay u ra xet
    104.      mark[u]=1;//danh dau da xet;
    105.      for(i=0;i<n;i++)
    106.          if(aMTK[u][i]!=0)//neu co duong di tu u->i
    107.              if(dodai[i]>dodai[u]+aMTK[u][i])
    108.                  /*neu tong cua khoang cach tu  dinh dang xet va trong
    109.                  so cua canh [u,i]
    110.                  be hon khoang cach hien tai*/
    111.              {
    112.                         dodai[i]=dodai[u]+aMTK[u][i];//gan cho no
    113.                         truoc[i]=u;//truoc i la u;
    114.              }
    115.  
    116.    }
    117.   for(j=1;j<=n;j++)
    118.   {
    119.         induongdi(source,j,truoc);
    120.         if(dodai[j]!=1000)
    121.             cout<<" :khoang cach tu : "<<source<<"--->"<<j<<" la :"<<dodai[j];
    122.  
    123.   }
    124.  
    125.  
    126. }
    127.  
    128.  
    129. int _tmain(int argc, _TCHAR* argv[])
    130. {
    131.     int source;
    132.     read("E:/DIJKSTRA.txt");
    133.     printffile();
    134.     cout<<"nhap dinh bat dau:";
    135.     cin>>source;
    136.     initdijksytra();//khoi tao
    137.     dodai[source]=0;//do dai cua dinh dang xet den dinh dang xet di nhien phai bang 0
    138.     dijkstra(source);
    139.     system("pause");
    140.     return 0;
    141. }
    Cho bạn luôn cái file đồ thì có dạng Dijkstra :đem về lưu vàO Ổ nào đó rồi chỉnh lại đừong dẫn.
    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

    lưu ý:mình dùng Số 0 đựoc ký hiệu tưong đương với dấu vô cùng nha bạn.(thừong trong sách hay dùng vô cùng)
    Đã được chỉnh sửa lần cuối bởi lethanh : 17-05-2009 lúc 03:43 PM.
    Every step I'm taking
    Every move I make
    Feels lost with no direction
    My faith is shaking
    But I gotta keep trying.

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

    OK OK Cảm ơn bạn nhiều

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

    Em mới nghiên cứu về C#.Xin hướng dẫn cài đặt thuật toán dijkstra tìm đường đi ngắn nhất giữa hai đỉnh bất kỳ trong đồ thị với ngôn ngữ C#

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

    Bạn ơi mình đang làm về thuật toán Dijkstra nhưng mình không rõ lắm. bạn có thể giải thích cho mình về tệp: DIJKSTRA.txt được không. Cảm ơn bạn nhiều!

  6. #6
    Ngày gia nhập
    12 2008
    Nơi ở
    Bình Dương
    Bài viết
    114

    Mặc định 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ị

    bạn có thể chỉ luôn về độ phức tạp của thuật toán này đi bạn! thanks!

  7. #7
    Ngày gia nhập
    02 2010
    Bài viết
    164

    Trích dẫn Nguyên bản được gửi bởi hoangedward Xem bài viết
    bạn có thể chỉ luôn về độ phức tạp của thuật toán này đi bạn! thanks!
    lấy cuốn thiết kế và đánh giá thuật toán của tác giả Trần Tuấn Minh ra mà xem

  8. #8
    Ngày gia nhập
    12 2008
    Nơi ở
    Bình Dương
    Bài viết
    114

    Trích dẫn Nguyên bản được gửi bởi anhtai116 Xem bài viết
    lấy cuốn thiết kế và đánh giá thuật toán của tác giả Trần Tuấn Minh ra mà xem
    mình có thể xem trong cuốn đó, nhưng sợ nói ra, các pác lại ko hiểu, lại trách mình nữa! hjhj!

  9. #9
    Ngày gia nhập
    10 2010
    Bài viết
    7

    mọi người giúp mình về tìm thuật toán Dijkstra bằng ngôn ngữ C# với.

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

    Wink Sửa code thuật toán Dijstra

    #include<conio.h>
    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>

    #define MAX 50
    #define TRUE 1
    #define FALSE 0
    int n,s,t;
    int truoc[MAX];//luu cac dinh truoc tai thoi diem dang xet cua dinh
    int d[MAX];//luu do dai duong di tu dinh bat dau den cac dinh con lai
    int DT[MAX][MAX];//do thi
    int cuoi[MAX];
    char chon;

    void nhap()
    {
    int i,j;
    printf("So dinh cua do thi: ");
    scanf("%d",&n);
    printf("\n Ma tran khoang cach");
    for (i=1;i<=n;i++)
    {
    printf("\n");
    for(j=1;j<=n;j++)
    {
    scanf("%d",&DT[i][j]);
    }
    }
    }

    void xuly()
    {
    int v,u,minp;
    printf("\n Tim duong di tu dinh s= ");
    scanf("%d",&s);
    printf(" den dinh: ");
    scanf("%d",&t);



    for(v=1;v<=n;v++)
    {
    d[v]=DT[s][v];
    truoc[v]=s;
    cuoi[v]=FALSE;
    }
    truoc[s]=0;
    d[s]=0;
    cuoi[s]=TRUE;
    while(!cuoi[t])
    {
    minp=1000;//khoi tao do dai tu dinh dang xet den cac dinh con la 999( xap xi vo cung)
    for(v=1;v<=n;v++)
    {
    if((!cuoi[v])&&(minp>d[v]))//neu dodai[v] nho hon min
    {
    u=v;
    minp=d[v];//min bang do dai cua dodai[i]
    }
    }
    cuoi[u]=TRUE;
    if(!cuoi[t])
    {
    for(v=1;v<=n;v++)
    {
    if((!cuoi[v])&&(d[u]+DT[u][v]<d[v]))
    {
    d[v]=d[u]+DT[u][v];
    }
    }
    }
    }

    }
    main()
    {
    int i,j;
    nhap();
    xuly();

    printf("\nDuong di ngan nhat tu %d den %d la\n",s,t);
    printf("%d <=",i);
    i=truoc[i];
    while(i!=s)
    {
    printf("%d <= ",i);
    i=truoc[i];
    }
    printf("%d",s);
    printf("\nDo dai duong di la: %d", d[t]);



    getch();
    }



    Mình đã nhìn mà mãi chẳng hiểu sai ở đâu! Help me!
    Thank iu mọi người nhìu nhìu trước nha!

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

  1. 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: 7
    Bài viết cuối: 04-11-2015, 06:14 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 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

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