fork download
copy 
  1. #include<bits/stdc++.h> 
  2. using namespace std; 
  3. # define INF 0x3f3f3f3f 
  4.  
  5. /* iPair ==> Integer Pair */
  6. typedef pair<int, int> iPair; 
  7.  
  8. /* This class represents a directed graph using */
  9. /* adjacency list representation */
  10. struct Graph 
  11. { 
  12. 	int V; /* No. of vertices */
  13.  
  14. 	/* In a weighted graph, we need to store vertex */
  15. 	/* and weight pair for every edge */
  16. 	list<iPair> *edges; 
  17. 	Graph(int V) 
  18.     { 
  19.         this->V = V; 
  20.         edges = new list<iPair> [V]; 
  21.     } 
  22.  
  23. 	/* function to add an edge to graph */
  24. 	void addEdge(int u, int v, int w) 
  25.     { 
  26.         edges[u].push_back(make_pair(v, w)); 
  27.         edges[v].push_back(make_pair(u, w)); 
  28.     }  
  29.  
  30. 	/* Print MST using Prim's algorithm */
  31. 	int primMST(); 
  32. }; 
  33.  
  34. /* Prints shortest paths from src to all other vertices */
  35. int Graph::primMST() 
  36. { 
  37. 	/* Create a priority queue to store vertices that 
  38. 	 are being preinMST. This is weird syntax in C++. 
  39. 	 Refer below link for details of this syntax 
  40. 	 http://g...content-available-to-author-only...z.com/implement-min-heap-using-stl/ */
  41. 	priority_queue< iPair, vector <iPair> , greater<iPair> > pq; 
  42.  
  43. 	int src = 0; // Taking vertex 0 as source*/ 
  44.  
  45. 	/* Create a vector for keys and initialize all 
  46. 	 keys as infinite (INF) */
  47. 	vector<int> key(V, INF); 
  48.  
  49. 	/* To store parent array which in turn store MST*/ 
  50. 	vector<int> parent(V, -1); 
  51.  
  52. 	/* To keep track of vertices included in MST */
  53. 	vector<bool> inMST(V, false); 
  54.  
  55. 	/* Insert source itself in priority queue and initialize 
  56. 	 its key as 0. */
  57. 	pq.push(make_pair(0, src)); 
  58. 	key[src] = 0; 
  59.  
  60. 	/* Looping till priority queue becomes empty */
  61. 	while (!pq.empty()) 
  62. 	{ 
  63. 		/* The first vertex in pair is the minimum key 
  64. 		vertex, extract it from priority queue. 
  65. 		vertex label is stored in second of pair (it 
  66. 		has to be done this way to keep the vertices 
  67. 		sorted key (key must be first item 
  68. 		in pair) */
  69. 		int u = pq.top().second; 
  70. 		pq.pop(); 
  71.  
  72. 		inMST[u] = true; // Include vertex in MST */
  73.  
  74. 		/*'i' is used to get all adjacent vertices of a vertex */
  75. 		list< pair<int, int> >::iterator i; 
  76. 		for (i = edges[u].begin(); i != edges[u].end(); ++i) 
  77. 		{ 
  78. 			/* Get vertex label and weight of current adjacent 
  79. 			 of u. */
  80. 			int v = (*i).first; 
  81. 			int weight = (*i).second; 
  82.  
  83. 			/* If v is not in MST and weight of (u,v) is smaller 
  84. 			than current key of v */
  85. 			if (inMST[v] == false && key[v] > weight) 
  86. 			{ 
  87. 				/*Updating key of v */
  88. 				key[v] = weight; 
  89. 				pq.push(make_pair(key[v], v)); 
  90. 				parent[v] = u; 
  91. 			} 
  92. 		} 
  93. 	} 
  94. 	int total = 0;
  95. 	/* Print edges of MST using parent array */
  96. 	for (int i = 1; i < V; ++i) {
  97.       for(auto k : edges[i]){
  98.        	if(k.first == parent[i])
  99.           total+=k.second;
  100.       }
  101.     }
  102.     return total;
  103. } 
  104. int findPathCost(vector<pair<int,int>> adj[], int u,int v){
  105.     for(auto it = adj[u].begin(); it != adj[u].end(); ++it){
  106.         if((*it).first == v){
  107.             return (*it).second;
  108.         }
  109.     }
  110. }
  111.  
  112. int isExistOpen(vector<pair<int,iPair>> open,int v){
  113.     for(auto it = open.begin(); it != open.end(); ++it){
  114.         if((*it).second.second == v){
  115.             return (*it).first;
  116.         }
  117.     }
  118. }
  119.  
  120. void findAndUpdate(vector<pair<int,iPair>> &open,int tc, int pc, int v){
  121.     for(auto it = open.begin(); it != open.end(); ++it){
  122.         if((*it).second.second == v){
  123.             (*it).second.first = pc;
  124.             (*it).first = tc;
  125.             return;
  126.         }
  127.     }
  128. }
  129.  
  130. int findMinh1(int *adj[], int v, vector<int> remainEle){
  131.     int mini = remainEle.size() > 1 ? INT_MAX : 0;
  132.     for(auto it = remainEle.begin(); it != remainEle.end(); ++it){
  133.         if(adj[v][*it] < mini && *it != v){
  134.             mini = adj[v][*it];
  135.         }
  136.     }
  137.     return mini;
  138. }
  139.  
  140. int findMinh2(int *adj[], int v, vector<int> remainEle){
  141.     int mini = remainEle.size() > 1 ? INT_MAX : 0;
  142.     for(auto it = remainEle.begin(); it != remainEle.end(); ++it){
  143.         if(adj[0][*it] < mini && *it != v){
  144.             mini = adj[0][*it];
  145.         }
  146.     }
  147.     return mini;
  148. }
  149.  
  150. int heuristicCost(int v, int *adj[], vector<int> remainEle){
  151.     int h1, h2, h3;
  152.     h1 = findMinh1(adj,v,remainEle);
  153.     h2 = findMinh2(adj,v,remainEle);
  154.  
  155.     Graph graph(remainEle.size()-1);
  156.     int i = 0, j = 0;
  157.     for(auto it = remainEle.begin(); it != remainEle.end(); ++it){
  158.         if(*it != v){
  159.             j = i+1;
  160.             for(auto jt = it+1; jt != remainEle.end(); ++jt){
  161.                 if(*jt != v){
  162.                     graph.addEdge(i,j,adj[*it][*jt]);
  163.                     ++j;
  164.                 }
  165.             }
  166.             ++i;
  167.         }
  168.     }
  169.     h3 = graph.primMST();
  170.     return h1+h2+h3;
  171.  
  172. }
  173.  
  174. int AStar(int **adj, int V){
  175.     vector<pair<int,iPair>> open;
  176.     vector<int> closed;
  177.     vector<int> remainEle;
  178.     for(int i = 0; i < V; ++i)
  179.         remainEle.push_back(i);
  180.     int hc = heuristicCost(0,adj,remainEle);
  181.       hc = heuristicCost(1,adj,remainEle);
  182.       hc = heuristicCost(2,adj,remainEle);
  183.  
  184.     int pc = 0;
  185.     int tc = hc + pc;
  186.      int minPathCost = 0;
  187.     open.push_back({tc,{pc,0}});
  188.     // while(!remainEle.empty()){
  189.     //     cout<<"hry";
  190.     //     auto mini = std::min_element(open.cbegin(), open.cend(), [](const auto& lhs, const auto& rhs) {
  191.     //         return lhs.first < rhs.first; 
  192.     //     });
  193.  
  194.     //     pair<int,iPair> storePair = *mini;
  195.     //     open.erase(mini);
  196.     //     int ppc = storePair.second.first;
  197.     //     int city = storePair.second.second;
  198.     //     closed.push_back(city);
  199.     //     remainEle.erase(find(remainEle.begin(),remainEle.end(),city));
  200.     //     if(remainEle.empty()){
  201.     //         minPathCost = ppc + adj[0][city];
  202.     //     }
  203.  
  204.     //     for(auto it = remainEle.begin(); it != remainEle.end(); ++it){
  205.     //         hc = heuristicCost((*it),adj,remainEle);
  206.     //         pc = ppc + adj[city][*it];
  207.     //         tc = pc + hc;
  208.     //         int existTCO = isExistOpen(open,(*it));
  209.  
  210.     //         if(existTCO != -1){
  211.     //             findAndUpdate(open,tc,pc,(*it));
  212.     //         }
  213.     //         else{
  214.     //             open.push_back({tc,{pc,(*it)}});
  215.     //         }
  216.     //     }
  217.  
  218.     // }
  219.     return hc;
  220. }
  221. /* Driver program to test methods of graph class */
  222. int main() 
  223. { 
  224. 	/* create the graph given in above fugure */
  225. 	int V;
  226.     cout << "Enter the no. of cities: ";
  227.     cin >> V;
  228.     int **adj;
  229.     adj = new int *[V];
  230.     for(int i = 0; i < V; i++)
  231.         adj[i] = new int[V];
  232.     cout << "Enter the path cost" << endl;
  233.     for(int i = 0; i < V; ++i){
  234.         for(int j = 0; j < V; ++j)
  235.             cin >> adj[i][j];
  236.     }
  237.     int minPathCost = AStar(adj,V);
  238.     cout << "optimal path cost: " << minPathCost << endl;
  239. 	return 0; 
  240. } 
  241.  
Success #stdin #stdout 0s 4380KB
comments (?)
stdin
copy 
4
0 1 5 6
1 0 8 2
5 8 0 7
6 2 7 0
stdout
copy 
Enter the no. of cities: Enter the path cost
optimal path cost: 8
https://ideone.com/Z4qHal
language:
C++14 (gcc 8.3)
created:
4 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!