SHARE
TWEET

Đường đi ngắn nhất

nguyenvanquan7826 Oct 12th, 2013 801 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cstdlib>
  4. #include <string>
  5. #include <cstring>
  6. #include <algorithm>
  7. #include <fstream>
  8. #include <sstream>
  9. #include <queue>
  10. #include <stack>
  11. #define INP "input.INP"
  12. #define OUT "output.OUT"
  13. using namespace std;
  14.  
  15. typedef int item;
  16. typedef struct GRAPH
  17. {
  18.         char *name;     // ten cac dinh
  19.         item **G;       // ma tran trong so
  20.         int n;          // so phan tu cua do thi
  21. } Graph;
  22.  
  23. void input_file(Graph &Gr);// lay du lieu tu file
  24. void input_B_E(Graph Gr, int &a, int &b); //nhap vao dinh dau va cuoi
  25. void output_file(Graph Gr);//Xuat ket qua tu file ra
  26. void Menu(int &select); //menu chon thuat toan
  27. int Dijkstra(Graph Gr, int a, int b);//thuat toan Dijkstra
  28. int number_or_char(Graph Gr); //nhap vao kiem tra la ky tu hay so va tra ve vi tri cua dinh trong do thi
  29. item tongthiethai(Graph Gr); //tong quang duong di cua moi dinh (thay the cho vo cung trong ma tran trong so)
  30. string convert_to_string(int number);//chuyen so number sang chuoi
  31. int floyd (Graph Gr, int a, int b);
  32.  
  33. int main()
  34. {
  35.         Graph Gr;
  36.         input_file(Gr);
  37.         int a, b, *P, i, select = 1;
  38.         output_file(Gr);
  39.         while (select)
  40.         {
  41.                 Menu(select);
  42.                 switch (select)
  43.                 {
  44.                         case 1:
  45.                         {
  46.                                 cout<<endl<<"-----Thuat toan Dijkstra-----"<<endl;
  47.                                 input_B_E(Gr, a, b);
  48.                                 Dijkstra(Gr, a, b);
  49.                                 system("pause");
  50.                                 break;
  51.                         }
  52.                         case 2:
  53.                         {
  54.                                 cout<<endl<<"-----Thuat toan Floy-----"<<endl;
  55.                                 input_B_E(Gr, a, b);
  56.                                 floyd (Gr, a, b);
  57.                                 system("pause");
  58.                                 break;
  59.                         }
  60.                 }
  61.                 if (select == 3) break;
  62.         }
  63.        
  64.         system("pause");
  65.         return 0;
  66. }
  67.  
  68. void input_file(Graph &Gr)
  69. {
  70.         ifstream inp(INP);
  71.         if (inp == NULL)
  72.         {
  73.                 cout<<"No found file input";
  74.                 return;
  75.         }
  76.         inp >> Gr.n ;
  77.        
  78.         Gr.name = new char [Gr.n];
  79.         for (int i=0; i<Gr.n; i++)
  80.                 inp >> Gr.name[i];
  81.         Gr.G = new int *[Gr.n];
  82.        
  83.         for (int i=0; i<Gr.n; i++)
  84.         {
  85.                 Gr.G[i] = new int [Gr.n];
  86.                 for (int j=0; j<Gr.n; j++)
  87.                         inp >> Gr.G[i][j];
  88.         }
  89.         inp.close();
  90. }
  91.  
  92. void input_B_E(Graph Gr, int &a, int &b)
  93. {
  94.         a = b = 0;
  95.         cout<<endl<<"Cac dinh danh so tu 1 den "<<Gr.n<<".Hoac tu "<<Gr.name[0]<<" den "<<Gr.name[Gr.n-1]<<endl;
  96.         cout<<"Nhap dinh bat dau : ";
  97.     while (a<1 || a> Gr.n)
  98.     {
  99.         cin>>a;
  100.         if (a<1 || a> Gr.n)
  101.                 cout<<"Khong hop le ! \nNhap lai dinh bat dau : ";
  102.     }
  103.    
  104.     cout<<"Nhap dinh ket thuc : ";
  105.     while (b<1 || b> Gr.n)
  106.     {
  107.         cin>>b;
  108.         if (b<1 || b> Gr.n)
  109.                 cout<<"Khong hop le ! \nNhap lai dinh ket thuc : ";
  110.     }
  111.     a -- ;
  112.     b -- ;
  113. }
  114.  
  115. void output_file(Graph Gr)
  116. {
  117.         //ofstream out(OUT);
  118.         fstream out;
  119.         out.open(OUT, ios::out|ios::trunc);
  120.         cout<<"Ma tran ke cua do thi"<<endl<<endl;
  121.         out<<"Ma tran ke cua do thi"<<endl<<endl;
  122.         for (int i=0; i<Gr.n; i++)
  123.         {
  124.                 cout<<setw(2)<<Gr.name[i];
  125.                 out<<setw(2)<<Gr.name[i];
  126.         }
  127.         out<<endl<<endl;
  128.         cout<<endl<<endl;
  129.         for (int i=0; i<Gr.n; i++)
  130.         {
  131.                 for (int j=0; j<Gr.n; j++)
  132.                 {
  133.                         cout<<setw(2)<<Gr.G[i][j];
  134.                         out<<setw(2)<<Gr.G[i][j];
  135.                 }
  136.                 cout<<endl;
  137.                 out<<endl;
  138.         }
  139.         out.close();
  140. }
  141.  
  142. //tong quang duong di cua moi dinh (thay the cho vo cung trong ma tran trong so)
  143. item tongthiethai(Graph Gr)
  144. {
  145.         item sum = 0;
  146.         for (int i=0; i<Gr.n; i++)
  147.                 for (int j=0; j<Gr.n; j++)
  148.                         sum += Gr.G[i][j];
  149.         return sum;
  150. }
  151.  
  152. void Menu(int &select)
  153. {
  154.         cout<<endl<<"Moi ban chon thuat toan :"<<endl;
  155.         cout<<"1: Thuat toan Dijkstra"<<endl;
  156.         cout<<"2: Thuat toan Floyd"<<endl;
  157.         cout<<"3: Thoat !"<<endl;
  158.         cin >> select;
  159. }
  160.  
  161. int Dijkstra(Graph Gr, int a, int b)
  162. {
  163.         fstream out;
  164.         out.open(OUT, ios::out|ios::app);
  165.         out<<endl<<"*****"<<endl;
  166.         // Len[i] - Gia tri nho nhat tu a -> i. Len1 danh dau do dai.
  167.         int Len[Gr.n];
  168.         int S[Gr.n];//Danh dau dinh thuoc danh sach dac biet
  169.         int P[Gr.n];//truy vet
  170.        
  171.         int max = tongthiethai(Gr);
  172.         fill (Len,Len+Gr.n,max); //Gan duong di ban dau = vo cung
  173.         fill (P,P+Gr.n,a);
  174.         fill (S,S+Gr.n,0); //Danh sach dac biet
  175.         Len[a] = 0;             // khoi tao do dai tu a->a = 0
  176.         int i = a, dem = 0, space = 10;
  177.        
  178.         //in ra hang tieu de
  179.         out<<setw(space/2)<<"TT |";
  180.         for (int i=0; i<Gr.n; i++)
  181.         {
  182.                 char s[100];
  183.                 sprintf(s,"%d%c%c%c",i+1,'(',Gr.name[i],')');
  184.                 out<<setw(space)<<s;
  185.         }
  186.         out <<endl;
  187.         for (int i=0; i< (space/2) + Gr.n*10; i++)
  188.                 out<<"-";
  189.         out<<endl;
  190.         //ket thuc in ra hang tieu de
  191.        
  192.         //while S<>V
  193.         for (int k=0; k<Gr.n; k++)
  194.         {
  195.                 dem ++;
  196.                 char *s = new char [100];
  197.                 char vocung = '~' , gach[10] = "  -  ";
  198.                 out<<setw(space/2-2)<<dem<<" |";
  199.                
  200.                 //tim do dai ngan nhat trong cac dinh          
  201.                 for (i=0; i<Gr.n; i++) // tim v thuoc (V-S) va Len[v] < vo cung
  202.                         if (!S[i] && Len[i] != max)
  203.                                 break;
  204.                 for (int j = i+1 ; j<Gr.n; j++) // tim dinh co Len min
  205.                         if (!S[j] && Len[j] < Len[i])
  206.                                 i = j;
  207.                 S[i] = 1;      
  208.                
  209.                 //----------In ra gia tri moi lan lap------------
  210.                 if (dem > 0)
  211.                         for (int j=0; j<Gr.n; j++)
  212.                         {
  213.                                 char temp[100];
  214.                                 strcpy(s," ");
  215.                                 if (dem >1 && j != i && S[j])
  216.                                         sprintf(s,"%c",'-');
  217.                                 else
  218.                                 {
  219.                                         if (j == i || (dem == 1 && j == a))
  220.                                                 strcat(s,"*");
  221.                                         strcat(s,"[");
  222.                                         if ( j != i && !S[j] && Len[j] == max)
  223.                                                 sprintf(temp,"%c,",vocung);
  224.                                         else
  225.                                                 sprintf(temp,"%d,",Len[j]);
  226.                                         strcat(s,temp);
  227.                                         if (j!=a && k==0)
  228.                                                 sprintf(temp, "%c", vocung);
  229.                                         else sprintf(temp, "%d", P[j]+1);      
  230.                                         strcat(s,temp);
  231.                                         strcat(s,"]");
  232.                                        
  233.                                 }
  234.                                 out<<setw(space)<<s;
  235.                         }
  236.                
  237.                 //----------Ket thuc In ra gia tri moi lan lap------------
  238.                
  239.                 //--------Tinh do dai tu dinh dang xet toi cac dinh tiep
  240.                
  241.                 for (int j = 0; j<Gr.n; j++) //thay doi do dai neu co
  242.                 {
  243.                         if (!S[j] && Gr.G[i][j])
  244.                                 if (Len[i] + Gr.G[i][j] < Len[j])
  245.                                 {
  246.                                         Len[j] = Len[i] + Gr.G[i][j];
  247.                                         P[j] = i; //truy vet
  248.                                 }
  249.                 }      
  250.                 out<<endl;                     
  251.         }
  252.        
  253.         //Ket luan duong di
  254.        
  255.         out<<endl<<"Do dai ngan nhat cua duong di tu "<<a+1<<"("<<Gr.name[a]<<")"
  256.                 <<" den "<<b+1<<"("<<Gr.name[b]<<")"<<" la "<<Len[b]<<endl;
  257.         out<<"Qua trinh duong di: ";
  258.         i = b;
  259.         char *s, *temp;
  260.         s = new char [Gr.n*10];
  261.         temp = new char [10];
  262.         sprintf(s,"%d",i+1);
  263.         while (i != a)
  264.         {
  265.                 sprintf(temp,"%s"," --> ");
  266.                 strcpy(s,strcat(temp,s));
  267.                 sprintf(temp,"%d",P[i] +1);
  268.                 strcpy(s,strcat(temp,s));
  269.                        
  270.                 i = P[i];
  271.         }      
  272.         out<<s<<endl;
  273.         cout<<"Hoan thanh ! Mo file output.out de xem ket qua !";
  274.         out.close();
  275.         return Len[b];
  276. }
  277.  
  278. int floyd (Graph Gr, int a, int b)
  279. {
  280.         fstream out;
  281.         out.open(OUT, ios::out|ios::app);
  282.         int max = tongthiethai(Gr);
  283.         int A[Gr.n][Gr.n], P[Gr.n][Gr.n];
  284.         for (int i=0; i<Gr.n; i++)
  285.                 for (int j=0; j<Gr.n; j++)
  286.                 {
  287.                         if (Gr.G[i][j])
  288.                                 A[i][j] = Gr.G[i][j];
  289.                         else A[i][j] = max;
  290.                         P[i][j] = -1;
  291.                 }
  292.                
  293.         for (int k=0; k<Gr.n; k++)
  294.         {
  295.                 out<<endl<<"Buoc thu "<<k<<endl;
  296.                 out<<setw(2*Gr.n)<<"A"<<setw(15+4*Gr.n)<<"P"<<endl;
  297.                 for (int i=0; i<Gr.n; i++)
  298.                 {
  299.                        
  300.                         for (int j=0; j<Gr.n; j++)
  301.                         {
  302.                                 char *temp = new char [50];
  303.                                 if (A[i][j] == max)
  304.                                         sprintf(temp,"%c",'~');
  305.                                 else
  306.                                         sprintf(temp,"%d",A[i][j]);
  307.                                
  308.                                 out<<setw(4)<<temp;
  309.                         }
  310.                                
  311.                         out<<setw(15)<<" ";
  312.                         for (int j=0; j<Gr.n; j++)
  313.                                 out<<setw(4)<<P[i][j] + 1;
  314.                         out<<endl;
  315.                 }
  316.                        
  317.                
  318.                 for (int i=0; i<Gr.n; i++)
  319.                         for (int j=0; j<Gr.n; j++)
  320.                                 if (A[i][j] > A[i][k] + A[k][j])
  321.                                 {
  322.                                         A[i][j] = A[i][k] + A[k][j];
  323.                                         P[i][j] = k ;
  324.                                 }      
  325.         }
  326.        
  327.         out<<endl<<"Do dai ngan nhat cua duong di tu "<<a+1<<"("<<Gr.name[a]<<")"<<" den "<<b+1<<"("<<Gr.name[b]<<")"<<" la "<<A[a][b]<<endl;
  328.         out<<"Qua trinh duong di: ";
  329.        
  330.         //truy vet
  331.         char *s, *temp;
  332.         s = new char [Gr.n*10];
  333.         temp = new char [10];
  334.         stack <item> S1;
  335.         stack <item> S2;
  336.         S1.push(a); //danh sach nap cac dinh vao
  337.         S1.push(b); //danh sach xuat cac dinh ra
  338.         int dich, tg;
  339.         while (!S1.empty())
  340.         {
  341.                 dich = S1.top(); //dich = phan tu dau tien
  342.                 S1.pop();               // dua phan tu do ra
  343.                 S2.push(dich); //cho vao danh sach xuat
  344.                 if (!S1.empty()) //trong khi S1 ko rong thi tiep tuc tim cac dinh
  345.                 {
  346.                         tg = S1.top();
  347.                         while (P[tg][dich] != -1) //tim cac dinh di tu tg den dich
  348.                         {
  349.                                 S1.push(P[tg][dich]);
  350.                                 tg = S1.top();
  351.                         }
  352.                 }
  353.         }
  354.        
  355.         sprintf(s,"%d",S2.top()+1);
  356.         S2.pop();
  357.        
  358.         while (!S2.empty())
  359.         {
  360.                 sprintf(temp,"%s%d"," --> ",S2.top()+1);
  361.                 strcat(s,temp);
  362.                 S2.pop();
  363.         }
  364.        
  365.         out<<s<<endl;
  366.         cout<<"Hoan thanh ! Mo file output.out de xem ket qua !";
  367.         out.close();
  368.        
  369.         return A[a][b];
  370.                
  371. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top