fork(1) download
copy 
  1. /*This is a complete and correctly functioning 
  2.   Shortest Path algorithm in C++ using Dijkstra's Algorithm.
  3.   For information on how Dijkstra's Algorithm works:
  4.   Visit the following link: https://w...content-available-to-author-only...e.com/watch?v=WN3Rb9wVYDY */
  5.   /*This Program was designed and constructed by (Mazhar Mustapha)*/
  6. #include <iostream>
  7. #include <string>
  8. #include <cstdlib>
  9. #include <vector>
  10. using namespace std;
  11.  
  12. struct node { // Struct is for node or letter in the diagram, each node has a value attached to it according to Dijkstra's algorithm
  13. 	char symbol; 
  14. 	int v;
  15. }; 
  16. struct path { // Struct is for path of each edge. Each edge has a specific length
  17. 	string movement;
  18. 	int L;
  19. };
  20. void display(node *, int, path *, int, char, char); // Neatly display results of input
  21. void test_path(char, char, path *, node *, int); // The actual process of testing and finding the shortest path
  22. int find_path_sub(path *, char, int); // Find subscript for path location.
  23. int find_path_sub_two(char); // Find subscript using last character in a string.
  24. int find_path_sub_third(char); // Find subscript using first character in a string.
  25. string find_path(char, node *, int); // Returns the deciphered string which had lowest path value.
  26. int main()
  27. {
  28. 	int x; char s, e;
  29. 	node *ptrN; path *ptrP;
  30. 	cout << "# of vertices: "; cin >> x; // Number of nodes
  31. 	const int n = x;
  32. 	ptrN = new node[n]; x = 97;
  33. 	for (int i = 0; i < n; i++)
  34. 	{
  35. 		ptrN[i].symbol = x; //Assigns a letter starting 'a' and increments to the defined number of n.
  36. 		x++;
  37. 	}
  38. 	cout << "Enter start and end: "; cin >> s >> e; // Start and Ending nodes, defined by its letter.
  39. 	for (int i = 0; i < n; i++)
  40. 	{
  41. 		if (s == ptrN[i].symbol)
  42. 			ptrN[i].v = 0; // Set starting node value to 0
  43. 		else
  44. 			ptrN[i].v = 9999999; // Set all other nodes to INFINITE.
  45. 	}
  46. 	cout << "Enter number of edges: "; cin >> x; // Number of connections
  47. 	const int m = x;
  48. 	ptrP = new path[m]; // Allocate number of paths needed.
  49. 	for (int i = 0; i < m; i++)
  50. 	{
  51. 		cin.ignore(20, '\n');
  52. 		cout << "[PATH] ";
  53. 		if (i == 0)
  54. 		{
  55. 			cout << "!ALPHABETICAL ORDER {EX. ab = (a to b)}"; // It is ESSENTIAL that the inputs here are entered in Alphebetical order, otherwise there will be errors.
  56. 		}
  57. 		cout << "| Edge " << (i + 1) << ": ";
  58. 		getline(cin, ptrP[i].movement);
  59. 		cout << "Length: "; cin >> ptrP[i].L;
  60. 	}
  61. 	display(ptrN, n, ptrP, m, s, e);
  62. 	test_path(s, e, ptrP, ptrN, m);
  63. 	delete[] ptrP;
  64. 	delete[] ptrN;
  65. 	system("PAUSE");
  66. 	return 0;
  67. }
  68. void display(node *PtrN, int n, path *PtrP, int m, char start, char end)
  69. {
  70. 	cout << "Vertices: ";
  71. 	for (int i = 0; i < n; i++)
  72. 	{
  73. 		cout << PtrN[i].symbol << " ";
  74. 	}
  75. 	cout << endl << "Start: " << start << endl << "End: " << end << endl;
  76. 	cout << "-----PATHS-----\n";
  77. 	for (int i = 0; i < m; i++)
  78. 	{
  79. 		cout << PtrP[i].movement;
  80. 		cout << " - [L] = " << PtrP[i].L;
  81. 		cout << endl;
  82. 	}
  83. }
  84. void test_path(char start, char end, path *ptr, node *Ptr, int m)
  85. {
  86. 	vector<int> record;
  87. 	vector<string> final;
  88. 	char begin = start; 
  89. 	int x, y, z, L;
  90. 	bool initial = true;
  91. 	string t, fpath;
  92. 	while (begin != end)
  93. 	{
  94. 		if(initial)
  95. 			x = find_path_sub(ptr, begin, m);
  96. 		initial = false;
  97. 		t = ptr[x].movement; // Set t with first path for while loop to activate.
  98. 		while (t[0] == begin && x < m)
  99. 		{
  100. 			y = find_path_sub_two(t[1]);
  101. 			z = find_path_sub_third(t[0]);
  102. 			Ptr[y].v = ptr[x].L + Ptr[z].v;
  103. 			record.push_back(Ptr[y].v);
  104. 			x++;
  105. 			if (x == m)
  106. 				continue;
  107. 			t = ptr[x].movement; // test while loop at the beginning.
  108. 		}
  109. 		if (record.size() != 0) {
  110. 			L = record[0];
  111. 			for (int i = 0; i < record.size(); i++)
  112. 			{
  113. 				if (record[i] < L)
  114. 					L = record[i];
  115. 			}
  116. 		}
  117. 		fpath = find_path(begin, Ptr, L);
  118. 		final.push_back(fpath);
  119. 		record.clear(); // Clear record for next loop.
  120. 		x = 0; // x equals 0 for safety purposes.
  121. 		initial = true; // Initial true for t to contain next path.
  122. 		begin = fpath[1]; // Begin ewuals the last character of the string. Example: a to b, now we need to start from b.
  123. 	}
  124. 	cout << "Final Path: ";
  125. 	for (int i = 0; i < final.size(); i++)
  126. 	{
  127. 		cout << final[i] << " ";
  128. 	}
  129. 	cout << endl;
  130. }
  131. int find_path_sub(path *ptr, char start, int size)
  132. {
  133. 	string temp;
  134. 	for (int i = 0; i < size; i++)
  135. 	{
  136. 		temp = ptr[i].movement;
  137. 		if (start == temp[0])
  138. 			return i;
  139. 	}
  140. }
  141. int find_path_sub_two(char last)
  142. {
  143. 	int j = 97;
  144. 	char test;
  145. 	for (int i = 0; ;i++)
  146. 	{
  147. 		test = j;
  148. 		if (test == last)
  149. 			return i;
  150. 		j++;
  151. 	}
  152. }
  153. int find_path_sub_third(char first)
  154. {
  155. 	int j = 97;
  156. 	char test;
  157. 	for (int i = 0; ;i++)
  158. 	{
  159. 		test = j;
  160. 		if (test == first)
  161. 			return i;
  162. 		j++;
  163. 	}
  164. }
  165. string find_path(char b, node *ptr, int value)
  166. {
  167. 	string f = "  ";
  168. 	f[0] = b;
  169. 	for (int i = 0; ;i++)
  170. 	{
  171. 		if (value == ptr[i].v)
  172. 		{
  173. 			f[1] = ptr[i].symbol;
  174. 			break;
  175. 		}
  176. 	}
  177. 	return f;
  178. }
Time limit exceeded #stdin #stdout 5s 113408KB
comments (?)
stdin
copy 
4
AB
5
AB
6
AC
3
BC
4
BD
1
CD
1
stdout
copy 
# of vertices: Enter start and end: Enter number of edges: [PATH] !ALPHABETICAL ORDER {EX. ab = (a to b)}| Edge 1: Length: [PATH] | Edge 2: Length: [PATH] | Edge 3: Length: [PATH] | Edge 4: Length: [PATH] | Edge 5: Length: Vertices: a b c d 
Start: A
End: B
-----PATHS-----
AB - [L] = 6
AC - [L] = 3
BC - [L] = 4
BD - [L] = 1
CD - [L] = 1
https://ideone.com/MLf6Xh
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!