fork(15) download
copy 
  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
comments (?)
stdin
copy 
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
copy 
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
copy 
sh: pause: not found
https://ideone.com/DpaGPW
Đường đi ngắn nhất
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!