fork(10) download
  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. }
  372.  
  373.  
Success #stdin #stdout #stderr 0s 3496KB
stdin
8
A B C D E F G H
0 3 5 2 0 0 0 0
3 0 1 0 7 0 0 0
5 1 0 4 0 1 0 0
2 0 4 0 0 3 6 0
0 7 0 0 0 2 0 3
0 0 1 3 2 0 4 6
0 0 0 6 0 4 0 5
0 0 0 0 3 6 5 0

1
stdout
No found file inputMa tran ke cua do thi




Moi ban chon thuat toan :
1: Thuat toan Dijkstra
2: Thuat toan Floyd
3: Thoat !

Moi ban chon thuat toan :
1: Thuat toan Dijkstra
2: Thuat toan Floyd
3: Thoat !
stderr
sh: pause: not found