Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 14 kết quả

Đề tài: Tìm đường đi ngắn nhất trên C++

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

    Mặc định Tìm đường đi ngắn nhất trên C++

    Đoạn code này dùng để tìm đường đi ngắn nhất giữa các thành phố.
    dữ liệu được nạp từ file text có tên "DataCity.txt" có nội dung như sau:
    from to khoangcach
    .........

    from : nơi đi
    to : nơi đến
    khoangcach: kieu int

    các giá trị cách nhau ít nhất một tab tương đương '\t' trong C,C++.

    C++ Code:
    1. #include<conio.h>
    2. #include<iostream.h>
    3. #include<stdio.h>
    4. #include<stdlib.h>
    5. #include<string.h>
    6. template<class Entry>
    7. struct Node
    8. {
    9.     Entry data;
    10.     Node *next;
    11. };
    12. template<class Entry>
    13. struct List
    14. {
    15.     Node<Entry> *first,*last;
    16. };
    17. struct Data1
    18. {
    19.     char *name;
    20.     int length;
    21. };
    22. struct Data2
    23. {
    24.     char *name;
    25.     List<Data1> *list;
    26. };
    27. struct Data3
    28. {
    29.     int sumlength;
    30.     List<Data1> *list;
    31. };
    32. template<class Entry>
    33. void AddNode(List<Entry>* list,Entry data)
    34. {
    35.     Node<Entry> *node=new Node<Entry>;
    36.     node->data=data;
    37.     node->next=NULL;
    38.     if(list->first==NULL)
    39.         list->first=list->last=node;
    40.     else {
    41.         list->last->next=node;
    42.         list->last=node;
    43.     }
    44. }
    45. void OutputData(List<Data2> *list)
    46. {
    47.     Node<Data2> *node1=list->first;
    48.     while(node1!=NULL)
    49.     {
    50.         cout<<"\n"<<node1->data.name<<"\n";
    51.         Node<Data1> *node2=node1->data.list->first;
    52.         while(node2!=NULL)
    53.         {
    54.             cout<<"\t-> "<<node2->data.name<<"\t"<<node2->data.length<<"\n";
    55.             node2=node2->next;
    56.         }
    57.         node1=node1->next;
    58.     }
    59. }
    60. void AddNodeList2(List<Data2>* list,char* from,char* to,int len)
    61. {
    62.   Data1 data1;
    63.   data1.name=to;
    64.   data1.length=len;
    65.   Node<Data2> *node=list->first;
    66.   while(node!=NULL)
    67.   {
    68.   if(strcmpi(node->data.name,from)==0)
    69.   {
    70.    AddNode(node->data.list,data1);
    71.    return;
    72.   }
    73.   node=node->next;
    74.   }
    75.   List<Data1> *temp=new List<Data1>;
    76.   temp->first=temp->last=NULL;
    77.   AddNode(temp,data1);
    78.   Data2 data;
    79.   data.name=from;
    80.   data.list=temp;
    81.   AddNode(list,data);
    82. }
    83. List<Data2>* ReadFile(char* filename)
    84. {
    85.   List<Data2> *list=new List<Data2>;
    86.   list->first=list->last=NULL;
    87.   FILE *fvb;
    88.   fvb=fopen(filename,"rt");
    89.   char str[255];
    90.   while(!feof(fvb))
    91.   {
    92.    fgets(str,255,fvb);
    93.    char *s[3];
    94.    int k=0,len=0,index=0;
    95.    for(int i=0;i<strlen(str);i++)
    96.    {
    97.     if(str[i]=='\n'||str[i]=='\t')
    98.     {
    99.     if(len>0)
    100.     {
    101.     char *s1=new char[len+1];
    102.     strncpy(s1,str+index,len+1);
    103.     s1[len]='\0';
    104.     s[k]=s1;
    105.     k++;
    106.     len=0;
    107.     }
    108.     index=i+1;
    109.     }
    110.     else len++;
    111.    }
    112.      AddNodeList2(list,s[0],s[1],atoi(s[2]));
    113.      AddNodeList2(list,s[1],s[0],atoi(s[2]));
    114.   }
    115.   fclose(fvb);
    116.   return list;
    117. }
    118.  
    119. void InsertNode(List<Data3> *list,Data3 data)
    120. {
    121.     Node<Data3> *node=new Node<Data3>;
    122.     node->data=data;
    123.     if(list->first==NULL)
    124.     {   list->first=list->last=node;
    125.         return;
    126.     }
    127.     Node<Data3> *temp=list->first;
    128.     Node<Data3> *pre=NULL;
    129.     while(temp!=NULL)
    130.     {
    131.         if(temp->data.sumlength>data.sumlength)
    132.         {
    133.             if(pre==NULL)
    134.             {
    135.               node->next=list->first;
    136.               list->first=node;
    137.             }
    138.             else
    139.             {node->next=temp;
    140.              pre->next=node;
    141.             }
    142.             return;
    143.         }
    144.         pre=temp;
    145.         temp=temp->next;
    146.     }
    147.     AddNode(list,data);
    148. }
    149. List<Data1>* CreateList(List<Data1> *list)
    150. {
    151.   List<Data1> *result=new List<Data1>;
    152.   result->first=result->last=NULL;
    153.   Node<Data1> *node=list->first;
    154.   while(node!=NULL)
    155.   {
    156.     Data1 data;
    157.     data=node->data;
    158.     AddNode(result,data);
    159.     node=node->next;
    160.   }
    161.   return result;
    162. }
    163. List<Data1>* getList(List<Data2> *list,char* from)
    164. {
    165.     Node<Data2> *node=list->first;
    166.     while(node!=NULL)
    167.     {
    168.         if(strcmpi(from,node->data.name)==0)
    169.             return node->data.list;
    170.         node=node->next;
    171.     }
    172.     return NULL;
    173. }
    174. List<Data1>* SearchRoad(List<Data2>* list,char* from,char* to)
    175. {
    176.     List<Data3> *queue=new List<Data3>;
    177.     queue->first=queue->last=NULL;
    178.  
    179.     List<Data1> *list1=new List<Data1>;
    180.     list1->first=list1->last=NULL;
    181.     Data1 data1;
    182.     data1.name=from;
    183.     data1.length=0;
    184.     AddNode(list1,data1);
    185.  
    186.     Data3 data3;
    187.     data3.sumlength=0;
    188.     data3.list=list1;
    189.     AddNode(queue,data3);
    190.     while(queue->first!=NULL)
    191.     {
    192.         Node<Data3> *node=queue->first;
    193.         queue->first=node->next;
    194.         char* str=node->data.list->last->data.name;
    195.         if(strcmpi(str,to)==0)
    196.             return node->data.list;
    197.         List<Data1> *l1=getList(list,str);
    198.         Node<Data1> *node1=l1->first;
    199.         while(node1!=NULL)
    200.         {
    201.             List<Data1> *newlist1=CreateList(node->data.list);
    202.             AddNode(newlist1,node1->data);
    203.             Data3 a;
    204.             a.sumlength=node->data.sumlength+node1->data.length;
    205.             a.list=newlist1;
    206.             InsertNode(queue,a);
    207.             node1=node1->next;
    208.         }
    209.     }
    210.     return NULL;
    211. }
    212. void OutputResult(List<Data1>*list,char* from,char* to)
    213. {
    214.     Node<Data1> *node=list->first;
    215.     cout<<endl<<node->data.name<<"(0)";
    216.     int kc=0;
    217.     node=node->next;
    218.     while(node!=NULL)
    219.     {
    220.         char* to=node->data.name;
    221.         int len=node->data.length;
    222.         kc+=len;
    223.         cout<<"--->"<<to<<"("<<len<<")";
    224.         node=node->next;
    225.     }
    226.     cout<<endl<<"Quang duong ngan nhat tu "<<from<<" den "<<to<<" la :"<<kc;
    227.  
    228. }
    229. void ShowListCity(List<Data2> *list)
    230. {
    231.  Node<Data2> *node=list->first;
    232.     cout<<"List City :\n";
    233.     while(node!=NULL)
    234.     {
    235.      cout<<"\n"<<node->data.name;
    236.      node=node->next;  
    237.     }
    238. }
    239. void main(char* filename)
    240. {
    241.     clrscr();
    242. //  ThuInsertNode();
    243.     if(strlen(filename)==0)
    244.         filename="DataCity.txt";
    245.     List<Data2> *list=ReadFile(filename);
    246.  
    247.     int key=0;
    248.     ShowListCity(list);
    249.     do
    250.        {
    251.     cout<<"\n";
    252.     char *from,*to;
    253.     from=new char[50];
    254.     to=new char[50];
    255.     cout<<"Input From City :";gets(from);
    256.     cout<<"Input To City   :";gets(to);
    257.  
    258.     List<Data1> *result=SearchRoad(list,from,to);
    259.  
    260.     cout<<"\n<--------Ket Qua-------->";
    261.     if(result!=NULL)
    262.     OutputResult(result,from,to);
    263.     else cout<<"\n Khong tim thay duong di tu "<<from<<" den "<<to;
    264.     cout<<"\nPress ESC to Exit !";
    265.     key=getch();
    266.        }while(key!=27);
    267.     getch();
    268. }


    có gì thắc mắc thì liên hệ với mình nhé !
    Đã được chỉnh sửa lần cuối bởi rox_rook : 05-04-2008 lúc 07:58 PM.

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

    Bạn ơi! Bài toán người đưa thư Trung Hoa áp dụng chương trình này được ko? Bạn có thể share source của nó được chứ? Thanks!

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

    Mình không biết bài toán người đưa thư Trung Hoa la gì cả bạn có thể cho mình biết nội dung của bài toán đó không.
    Ah bạn đã chạy thử đoạn code trên chưa !
    nếu chạy rồi thì bạn thử sử dụng nó để giải quyết bài toán trên của bạn.

  4. #4
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Bài trên bạn làm theo thuật toán gì vậy, mình đọc không hiểu, trông giống như tìm đường chứ không giống tìm đường ngắn nhất.

  5. #5
    Ngày gia nhập
    10 2007
    Bài viết
    13

    CT trên là tìm đường đi ngắn nhất TT Dijsktra.
    Còn bài toán người đưa thư Trung Hoa (Chinese Postman Problem) là: "Người đưa thư cần tìm đường đi ngắn nhất đi qua mọi cạnh ít nhất một lần sao cho quãng đường đi là ngắn nhât". Nó phát triển từ đường đi Euler nhưng có trọng số.
    Hic.

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

    Mặc định Tìm đường đi ngắn nhất trên C++

    chào bạn ! bạn có thể lấy một ví dụ về file "datacity.txt" được không ? mình mới bắt đầu học c++ nên không hiểu lắm . cảm ơn bạn trước nhé !

  7. #7
    Ngày gia nhập
    04 2007
    Nơi ở
    Bà Trưng quê ở Mê Linh
    Bài viết
    29

    Bạn ơi ! Bạn muốn hiểu về "datacity.txt" thì bạn phải hiểu về tập tin. Vậy bạn hãy đọc phần Tập tin này trong Chương 14 Kiểu dữ liệu có cấu trúc: Kiểu dữ liệu tệp (FILE) trong Ngôn Ngữ Lập Trình C của Quách Tuấn Ngọc hoặc Tệp tin trong NNLT C++ của Phạm Văn Ất. Rồi bạn thực hành theo ví dụ đã cho một vài lần mình nghĩ bạn sẽ hiểu được. Chúc bạn thành công.
    Đã được chỉnh sửa lần cuối bởi kscntt_46 : 04-04-2008 lúc 11:36 AM. Lý do: sua
    >"<

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

    Bạn ơi, Bạn pót file text có tên "DataCity.txt" lên lun nhe. Thanks!

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

    mình rất cần chương trình bài toán người đưa thư (chu trình euler); chưa giải quyết dc phần các đỉnh bậc lẻ
    giúp mình với nhé
    rất cần

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

    Trích dẫn Nguyên bản được gửi bởi lammcathay Xem bài viết
    CT trên là tìm đường đi ngắn nhất TT Dijsktra.
    Còn bài toán người đưa thư Trung Hoa (Chinese Postman Problem) là: "Người đưa thư cần tìm đường đi ngắn nhất đi qua mọi cạnh ít nhất một lần sao cho quãng đường đi là ngắn nhât". Nó phát triển từ đường đi Euler nhưng có trọng số.
    Hic.
    mình biết nhưng tìm chu trình chứ không phải đường đi
    Nội dung: một nhân viên bưu điện đi từ thành phố này đến các thành phố khác để phát thư, rồi quay về lại thành phố nơi xuất phát. tìm chu trình sao cho đường đi ngắn nhất

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

  1. Lập trình C Lập trình song song sử dụng MPI trên linux để tìm đường di ngắn nhất dijkstra?
    Gửi bởi lploc503 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 26-10-2012, 09:36 PM
  2. Trả lời: 1
    Bài viết cuối: 08-11-2011, 11:05 PM
  3. Trả lời: 0
    Bài viết cuối: 03-06-2011, 08:35 PM
  4. Thảo luận về thuật toán tìm đường đi ngắn nhất (có chi phí ít nhất) trên ma trận
    Gửi bởi hunterphu trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 10-08-2010, 12:05 AM
  5. Tiềm đường đi ngắn nhất trên đồ thị
    Gửi bởi sirkhocnhe trong diễn đàn Thắc mắc lập trình Visual C++
    Trả lời: 0
    Bài viết cuối: 25-03-2010, 11:24 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