fork(5) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int getPreviousVertex(int *mas, int vertex) 
  6. {
  7. 	return mas[vertex];
  8. }
  9.  
  10. int main(void) {
  11. 	std::vector<int> mas; 
  12. 	const int N = 9;
  13.  
  14.     int pre[N],start = 3, D[N];
  15. 	int g=1000; //бесконечность
  16.     bool flag[N];
  17.  
  18.     int A[N][N] = {
  19.         {0, 1, g, 5, 1, g, g, 1, g},
  20.         {1, 0, 7, 4, g, g, g, g, g},
  21.         {g, 7, 0, g, g, 2, 1, g, g},
  22.         {5, 4, g, 0, g, 8, g, g, g},
  23.         {1, g, g, g, 0, g, g, 1, g},
  24.         {g, g, 2, 8, g, 0, 4, g, 4},
  25. 		{g, g, 1, g, g, 4, 0, g, 4},
  26. 		{g, g, g, g, g, g, g, g, g},
  27. 		{g, g, g, g, g, g, g, g, g},
  28.     };
  29. 	string names[N] = {"R1","R2","R3","R4","R5","R6","R7","N1","N2"};
  30. 	string edges[N][N] = {
  31.          {"0", "A", "0", "B", "E", "0", "0", "P1", "0"},
  32.          {"A", "0", "D", "I", "0", "0", "0", "0", "0"},
  33.          {"0", "D", "0", "0", "0", "H", "F", "0", "0"},
  34.          {"B", "I", "0", "0", "0", "H", "0", "0", "0"},
  35.          {"E", "0", "0", "0", "0", "0", "0", "P2", "0"},
  36.          {"0", "0", "H", "H", "0", "0", "0", "0", "P4"},
  37.          {"0", "0", "F", "0", "0", "0", "0", "0", "P3"},
  38.          {"0", "0", "0", "0", "0", "0", "0", "0", "0"},
  39.          {"0", "0", "0", "0", "0", "0", "0", "0", "0"},
  40. 	 };
  41.  
  42.     for (int i = 0; i < N; i++) {
  43.         pre[i] = start;
  44.         flag[i] = false;
  45.         D[i] = A[start][i];
  46.     }
  47.  
  48.     flag[start] = true;
  49.     pre[start] = 0;
  50.     for (int i = 0; i < N ; i++) {
  51.         int k = 0;
  52.         int minras = g;
  53.         // Находим минимальное расстояние до непомеченных вершин
  54.         for (int j = 0; j < N; j++) {
  55.             if (!flag[j] && minras > D[j]) {
  56.                 minras = D[j];
  57.                 k = j;
  58.             }
  59.         }
  60.         // Вершина k помечается просмотренной
  61.         flag[k] = true;
  62.         for (int j = 0; j < N; j++) {
  63.             if (!flag[j] && D[j] > D[k] + A[k][j]) {
  64.                 D[j] = D[k] + A[k][j];
  65.                 pre[j] = k;
  66.             }
  67.         }
  68.     }
  69.  
  70. 	int size;
  71.     int curVertex, prevVertex, sourceVertex = start, myVertex, tmp;
  72.     for(int i = 0; i<N; i++) {
  73.     	int m = 0;
  74.     	curVertex = i;
  75.     	myVertex = curVertex;
  76.     	if (sourceVertex != curVertex) 
  77.     	{
  78. 			do
  79. 	    	{
  80. 	        	mas.push_back(curVertex);
  81. 	        	prevVertex = getPreviousVertex(pre, curVertex);
  82. 	        	curVertex = prevVertex;
  83. 	        	m++;
  84. 		 	} while (curVertex != sourceVertex);
  85. 		 	mas.push_back(curVertex);
  86. 			size = mas.size();
  87. 			cout << "Distance to " << names[myVertex] << ": " << D[myVertex] << "; Path: ";
  88. 			for (int j=size-1; j>=0; j--) 
  89. 			{
  90. 				tmp = mas[j];
  91. 				if(size-1 == j) 
  92. 				{
  93. 					cout << names[tmp];
  94. 				}
  95. 				else
  96. 				{
  97. 					int prev = mas[j+1], next = mas[j];
  98. 					cout << " -(" << edges[prev][next] << ")-> " << names[tmp];
  99. 				}
  100. 				mas.pop_back();
  101. 			}
  102. 			cout << endl;
  103. 		}
  104. 	}
  105. }
  106.  
Success #stdin #stdout 0s 2824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Distance to R1: 5; Path: R4 -(B)-> R1
Distance to R2: 4; Path: R4 -(I)-> R2
Distance to R3: 10; Path: R4 -(H)-> R6 -(H)-> R3
Distance to R5: 6; Path: R4 -(B)-> R1 -(E)-> R5
Distance to R6: 8; Path: R4 -(H)-> R6
Distance to R7: 11; Path: R4 -(H)-> R6 -(H)-> R3 -(F)-> R7
Distance to N1: 6; Path: R4 -(B)-> R1 -(P1)-> N1
Distance to N2: 12; Path: R4 -(H)-> R6 -(P4)-> N2
https://ideone.com/ZMiVPE
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 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!