· 8 years ago · Apr 05, 2018, 01:32 PM
1// Program to find Dijkstra's shortest path using
2// priority_queue in STL
3#include<bits/stdc++.h>
4using namespace std;
5# define INF 0x3f3f3f3f
6
7// iPair ==> Integer Pair
8typedef pair<int, int> iPair;
9
10// This class represents a directed graph using
11// adjacency list representation
12class Graph
13{
14 int V; // No. of vertices
15
16 // In a weighted graph, we need to store vertex
17 // and weight pair for every edge
18 list< pair<int, int> > *adj;
19
20public:
21 Graph(int V); // Constructor
22
23 // function to add an edge to graph
24 void addEdge(int u, int v, int w);
25
26 // prints shortest path from s
27 void shortestPath(int s);
28};
29
30// Allocates memory for adjacency list
31Graph::Graph(int V)
32{
33 this->V = V;
34 adj = new list<iPair> [V];
35}
36
37void Graph::addEdge(int u, int v, int w)
38{
39 adj[u].push_back(make_pair(v, w));
40 adj[v].push_back(make_pair(u, w));
41}
42
43// Prints shortest paths from src to all other vertices
44void Graph::shortestPath(int src)
45{
46 // Create a priority queue to store vertices that
47 // are being preprocessed. This is weird syntax in C++.
48 // Refer below link for details of this syntax
49 // http://geeksquiz.com/implement-min-heap-using-stl/
50 priority_queue< iPair, vector <iPair> , greater<iPair> > pq;
51
52 // Create a vector for distances and initialize all
53 // distances as infinite (INF)
54 vector<int> dist(V, INF);
55
56 // Insert source itself in priority queue and initialize
57 // its distance as 0.
58 pq.push(make_pair(0, src));
59 dist[src] = 0;
60
61 /* Looping till priority queue becomes empty (or all
62 distances are not finalized) */
63 while (!pq.empty())
64 {
65 // The first vertex in pair is the minimum distance
66 // vertex, extract it from priority queue.
67 // vertex label is stored in second of pair (it
68 // has to be done this way to keep the vertices
69 // sorted distance (distance must be first item
70 // in pair)
71 int u = pq.top().second;
72 pq.pop();
73
74 // 'i' is used to get all adjacent vertices of a vertex
75 list< pair<int, int> >::iterator i;
76 for (i = adj[u].begin(); i != adj[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 there is shorted path to v through u.
84 if (dist[v] > dist[u] + weight)
85 {
86 // Updating distance of v
87 dist[v] = dist[u] + weight;
88 pq.push(make_pair(dist[v], v));
89 }
90 }
91 }
92
93 // Print shortest distances stored in dist[]
94 printf("Vertex Distance from Source\n");
95 for (int i = 0; i < V; ++i)
96 printf("%d \t\t %d\n", i, dist[i]);
97}
98
99// Driver program to test methods of graph class
100int main()
101{
102 // create the graph given in above fugure
103 int V = 9;
104 Graph g(V);
105
106 // making above shown graph
107 g.addEdge(0, 1, 4);
108 g.addEdge(0, 7, 8);
109 g.addEdge(1, 2, 8);
110 g.addEdge(1, 7, 11);
111 g.addEdge(2, 3, 7);
112 g.addEdge(2, 8, 2);
113 g.addEdge(2, 5, 4);
114 g.addEdge(3, 4, 9);
115 g.addEdge(3, 5, 14);
116 g.addEdge(4, 5, 10);
117 g.addEdge(5, 6, 2);
118 g.addEdge(6, 7, 1);
119 g.addEdge(6, 8, 6);
120 g.addEdge(7, 8, 7);
121
122 g.shortestPath(0);
123
124 return 0;
125}
126
127Output :
128
129Vertex Distance from Source
1300 0
1311 4
1322 12
1333 19
1344 21
1355 11
1366 9
1377 8
1388 14
139
140_______________________________________________________________________________________________________________________________________________________________
141
142Input : Graph
143 u, v, color
144 1, 2, 1
145 1, 3, 2
146 2, 3, 3
147 2, 4, 2
148 2, 5, 4
149 3, 5, 3
150 4, 5, 2
151source = 2 destination = 5
152
153Output : 3
154Explanation : There are three paths from 2 to 5
1552 -> 5 with color red
1562 -> 3 - > 5 with color sky blue
1572 -> 4 - > 5 with color green
158
159// C++ code to find unicolored paths
160#include <bits/stdc++.h>
161using namespace std;
162
163const int MAX_V = 100;
164
165int color[MAX_V];
166bool vis[MAX_V];
167
168// Graph class represents a udirected graph
169// using adjacency list representation
170class Graph
171{
172 // vertices, edges, adjancy list
173 int V;
174 int E;
175 vector<pair<int, int> > adj[MAX_V];
176
177 // function used by UniColorPaths
178 // DFS traversal o from x to y
179 void dfs(int x, int y, int z);
180
181// Constructor
182public:
183 Graph(int V, int E);
184
185 // function to add an edge to graph
186 void addEdge(int v, int w, int z);
187
188 // finds paths between a and b having
189 // same color edges
190 int UniColorPaths(int a, int b);
191};
192
193Graph::Graph(int V, int E)
194{
195 this -> V = V;
196 this -> E = E;
197}
198
199void Graph::addEdge(int a, int b, int c)
200{
201 adj[a].push_back({b, c}); // Add b to a’s list.
202 adj[b].push_back({a, c}); // Add c to b’s list.
203}
204
205void Graph::dfs(int x, int y, int col)
206{
207 if (vis[x])
208 return;
209 vis[x] = 1;
210
211 // mark this as a possible color to reach s to d
212 if (x == y)
213 {
214 color[col] = 1;
215 return;
216 }
217
218 // if the next edge is also of same color
219 for (int i = 0; i < int(adj[x].size()); i++)
220 if (adj[x][i].second == col)
221 dfs(adj[x][i].first, y, col);
222}
223
224// function that finds paths between a and b
225// such that all edges are same colored
226// It uses recursive dfs()
227int Graph::UniColorPaths(int a, int b)
228{
229
230 // dfs on nodes directly connected to source
231 for (int i = 0; i < int(adj[a].size()); i++)
232 {
233 dfs(a, b, adj[a][i].second);
234
235 // to visit again visited nodes
236 memset(vis, 0, sizeof(vis));
237 }
238
239 int cur = 0;
240 for (int i = 0; i <= E; i++)
241 cur += color[i];
242
243 return (cur);
244}
245
246// driver code
247int main()
248{
249 // Create a graph given in the above diagram
250 Graph g(5, 7);
251 g.addEdge(1, 2, 1);
252 g.addEdge(1, 3, 2);
253 g.addEdge(2, 3, 3);
254 g.addEdge(2, 4, 2);
255 g.addEdge(2, 5, 4);
256 g.addEdge(3, 5, 3);
257 g.addEdge(4, 5, 2);
258
259 int s = 2; // source
260 int d = 5; // destination
261
262 cout << "Number of unicolored paths : ";
263 cout << g.UniColorPaths(s, d) << endl;
264 return 0;
265}
266
267Output:
268
269Number of unicolored paths : 3
270
271Time Complexity : O(E * (E + V))
272
273________________________________________________________________________________________________________________________________________________________________
274
275Given an adjacency matrix representation of an undirected graph. Find if there is any Eulerian Path in the graph. If there is no path print “No Solutionâ€. If there is any path print the path.
276
277Examples:
278
279Input : [[0, 1, 0, 0, 1],
280 [1, 0, 1, 1, 0],
281 [0, 1, 0, 1, 0],
282 [0, 1, 1, 0, 0],
283 [1, 0, 0, 0, 0]]
284
285Output : 5 -> 1 -> 2 -> 4 -> 3 -> 2
286
287Input : [[0, 1, 0, 1, 1],
288 [1, 0, 1, 0, 1],
289 [0, 1, 0, 1, 1],
290 [1, 1, 1, 0, 0],
291 [1, 0, 1, 0, 0]]
292Output : "No Solution"
293 # Efficient python program to find out Eulerian path
294
295# Function to find out the path
296# It takes the adjacency matrix representation of the
297# graph as input
298def findpath(graph):
299 n = len(graph)
300 numofadj = list()
301
302 # Find out number of edges each vertex has
303 for i in range(n):
304 numofadj.append(sum(graph[i]))
305
306 # Find out how many vertex has odd number edges
307 startpoint = 0
308 numofodd = 0
309 for i in range(n-1, -1, -1):
310 if (numofadj[i] % 2 == 1):
311 numofodd += 1
312 startpoint = i
313
314 # If number of vertex with odd number of edges
315 # is greater than two return "No Solution".
316 if (numofodd > 2):
317 print("No Solution")
318 return
319
320 # If there is a path find the path
321 # Initialize empty stack and path
322 # take the starting current as discussed
323 stack = list()
324 path = list()
325 cur = startpoint
326
327 # Loop will run until there is element in the stack
328 # or current edge has some neighbour.
329 while(stack != [] or sum(graph[cur]) != 0):
330
331 # If current node has not any neighbour
332 # add it to path and pop stack
333 # set new current to the popped element
334 if (sum(graph[cur]) == 0):
335 path.append(cur + 1)
336 cur = stack.pop(-1)
337
338 # If the current vertex has at least one
339 # neighbour add the current vertex to stack,
340 # remove the edge between them and set the
341 # current to its neighbour.
342 else:
343 for i in range(n):
344 if graph[cur][i] == 1:
345 stack.append(cur)
346 graph[cur][i] = 0
347 graph[i][cur] = 0
348 cur = i
349 break
350 # print the path
351 for ele in path:
352 print(ele, "-> ", end = '')
353 print(cur + 1)
354
355# Driver Program
356# Test case 1
357graph1 = [[0, 1, 0, 0, 1],
358 [1, 0, 1, 1, 0],
359 [0, 1, 0, 1, 0],
360 [0, 1, 1, 0, 0],
361 [1, 0, 0, 0, 0]]
362findpath(graph1)
363
364# Test case 2
365graph2 = [[0, 1, 0, 1, 1],
366 [1, 0, 1, 0, 1],
367 [0, 1, 0, 1, 1],
368 [1, 1, 1, 0, 0],
369 [1, 0, 1, 0, 0]]
370findpath(graph2)
371
372# Test case 3
373graph3 = [[0, 1, 0, 0, 1],
374 [1, 0, 1, 1, 1],
375 [0, 1, 0, 1, 0],
376 [0, 1, 1, 0, 1],
377 [1, 1, 0, 1, 0]]
378findpath(graph3)
379
380Output:
381
3824 -> 0 -> 1 -> 3 -> 2 -> 1
383No Solution
3844 -> 3 -> 2 -> 1 -> 4 -> 0 -> 1 -> 3
385
386________________________________________________________________________________________________________________________________________________________________________________________________________________
387/* C/C++ program for solution of Hamiltonian Cycle problem
388 using backtracking */
389#include<stdio.h>
390
391// Number of vertices in the graph
392#define V 5
393
394void printSolution(int path[]);
395
396/* A utility function to check if the vertex v can be added at
397 index 'pos' in the Hamiltonian Cycle constructed so far (stored
398 in 'path[]') */
399bool isSafe(int v, bool graph[V][V], int path[], int pos)
400{
401 /* Check if this vertex is an adjacent vertex of the previously
402 added vertex. */
403 if (graph [ path[pos-1] ][ v ] == 0)
404 return false;
405
406 /* Check if the vertex has already been included.
407 This step can be optimized by creating an array of size V */
408 for (int i = 0; i < pos; i++)
409 if (path[i] == v)
410 return false;
411
412 return true;
413}
414
415/* A recursive utility function to solve hamiltonian cycle problem */
416bool hamCycleUtil(bool graph[V][V], int path[], int pos)
417{
418 /* base case: If all vertices are included in Hamiltonian Cycle */
419 if (pos == V)
420 {
421 // And if there is an edge from the last included vertex to the
422 // first vertex
423 if ( graph[ path[pos-1] ][ path[0] ] == 1 )
424 return true;
425 else
426 return false;
427 }
428
429 // Try different vertices as a next candidate in Hamiltonian Cycle.
430 // We don't try for 0 as we included 0 as starting point in in hamCycle()
431 for (int v = 1; v < V; v++)
432 {
433 /* Check if this vertex can be added to Hamiltonian Cycle */
434 if (isSafe(v, graph, path, pos))
435 {
436 path[pos] = v;
437
438 /* recur to construct rest of the path */
439 if (hamCycleUtil (graph, path, pos+1) == true)
440 return true;
441
442 /* If adding vertex v doesn't lead to a solution,
443 then remove it */
444 path[pos] = -1;
445 }
446 }
447
448 /* If no vertex can be added to Hamiltonian Cycle constructed so far,
449 then return false */
450 return false;
451}
452
453/* This function solves the Hamiltonian Cycle problem using Backtracking.
454 It mainly uses hamCycleUtil() to solve the problem. It returns false
455 if there is no Hamiltonian Cycle possible, otherwise return true and
456 prints the path. Please note that there may be more than one solutions,
457 this function prints one of the feasible solutions. */
458bool hamCycle(bool graph[V][V])
459{
460 int *path = new int[V];
461 for (int i = 0; i < V; i++)
462 path[i] = -1;
463
464 /* Let us put vertex 0 as the first vertex in the path. If there is
465 a Hamiltonian Cycle, then the path can be started from any point
466 of the cycle as the graph is undirected */
467 path[0] = 0;
468 if ( hamCycleUtil(graph, path, 1) == false )
469 {
470 printf("\nSolution does not exist");
471 return false;
472 }
473
474 printSolution(path);
475 return true;
476}
477
478/* A utility function to print solution */
479void printSolution(int path[])
480{
481 printf ("Solution Exists:"
482 " Following is one Hamiltonian Cycle \n");
483 for (int i = 0; i < V; i++)
484 printf(" %d ", path[i]);
485
486 // Let us print the first vertex again to show the complete cycle
487 printf(" %d ", path[0]);
488 printf("\n");
489}
490
491// driver program to test above function
492int main()
493{
494 /* Let us create the following graph
495 (0)--(1)--(2)
496 | / \ |
497 | / \ |
498 | / \ |
499 (3)-------(4) */
500 bool graph1[V][V] = {{0, 1, 0, 1, 0},
501 {1, 0, 1, 1, 1},
502 {0, 1, 0, 0, 1},
503 {1, 1, 0, 0, 1},
504 {0, 1, 1, 1, 0},
505 };
506
507 // Print the solution
508 hamCycle(graph1);
509
510 /* Let us create the following graph
511 (0)--(1)--(2)
512 | / \ |
513 | / \ |
514 | / \ |
515 (3) (4) */
516 bool graph2[V][V] = {{0, 1, 0, 1, 0},
517 {1, 0, 1, 1, 1},
518 {0, 1, 0, 0, 1},
519 {1, 1, 0, 0, 0},
520 {0, 1, 1, 0, 0},
521 };
522
523 // Print the solution
524 hamCycle(graph2);
525
526 return 0;
527}
528
529Output:
530
531Solution Exists: Following is one Hamiltonian Cycle
532 0 1 2 4 3 0
533
534Solution does not exist
535
536Note that the above code always prints cycle starting from 0. Starting point should not matter as cycle can be started from any point. If you want to change the starting point, you should make two changes to above code.
537Change “path[0] = 0;†to “path[0] = s;†where s is your new starting point. Also change loop “for (int v = 1; v < V; v++)" in hamCycleUtil() to "for (int v = 0; v < V; v++)". Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
538
539________________________________________________________________________________________________________________________________________________________________________________________________________________
540Given an integer n(>=2), find a permutation of numbers from 1 to n such that the sum of two consecutive numbers of that permutation is a perfect square. If that kind of permutation is not possible to print “No Solutionâ€.
541
542Examples:
543
544Input : 17
545Output : [16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8, 17]
546Explanation : 16+9 = 25 = 5*5, 9+7 = 16 = 4*4, 7+2 = 9 = 3*3 and so on.
547
548Input: 20
549Output: No Solution
550
551Input : 25
552Output : [2, 23, 13, 12, 24, 25, 11, 14, 22, 3, 1, 8,
553 17, 19, 6, 10, 15, 21, 4, 5, 20, 16, 9, 7, 18]
554
555# Python3 program for Sum-square series using
556# hamiltonian path concept and backtracking
557
558# Function to check wheter we can add number
559# v with the path in the position pos.
560def issafe(v, graph, path, pos):
561
562 # if there is no edge between v and the
563 # last element of the path formed so far
564 # return false.
565 if (graph[path[pos - 1]][v] == 0):
566 return False
567
568 # Otherwise if there is an edge between
569 # v and last element of the path formed so
570 # far, then check all the elements of the
571 # path. If v is already in the path return
572 # false.
573 for i in range(pos):
574
575 if (path[i] == v):
576 return False
577
578 # If none of the previous cases satisfies
579 # then we can add v to the path in the
580 # position pos. Hence return true.
581 return True
582
583# Function to form a path based on the graph.
584def formpath(graph, path, pos):
585
586 # If all the elements are included in the
587 # path i.e. length of the path is n then
588 # return true i.e. path formed.
589 n = len(graph) - 1
590 if (pos == n + 1):
591 return True
592
593 # This loop checks for each element if it
594 # can be fitted as the next element of the
595 # path and recursively finds the next
596 # element of the path.
597 for v in range(1, n + 1):
598
599 if issafe(v, graph, path, pos):
600 path[pos] = v
601
602 # Recurs for next element of the path.
603 if (formpath(graph, path, pos + 1) == True):
604 return True
605
606 # If adding v does not give a solution
607 # then remove it from path
608 path[pos] = -1
609
610 # if any vertex cannot be added with the
611 # formed path then return false and
612 # backtracks.
613 return False
614
615# Function to find out sum-square series.
616def hampath(n):
617
618 # base case: if n = 1 there is no solution
619 if n == 1:
620 return 'No Solution'
621
622 # Make an array of perfect squares from 1
623 # to (2 * n-1)
624 l = list()
625
626 for i in range(1, int((2 * n-1) ** 0.5) + 1):
627 l.append(i**2)
628
629 # Form the graph where sum of two adjacent
630 # vertices is a perfect square
631 graph = [[0 for i in range(n + 1)] for j in range(n + 1)]
632
633 for i in range(1, n + 1):
634 for ele in l:
635
636 if ((ele-i) > 0 and (ele-i) <= n
637 and (2 * i != ele)):
638 graph[i][ele - i] = 1
639 graph[ele - i][i] = 1
640
641 # strating from 1 upto n check for each
642 # element i if any path can be formed
643 # after taking i as the first element.
644 for j in range(1, n + 1):
645 path = [-1 for k in range(n + 1)]
646 path[1] = j
647
648 # If starting from j we can form any path
649 # then we will return the path
650 if formpath(graph, path, 2) == True:
651 return path[1:]
652
653 # If no path can be formed at all return
654 # no solution.
655 return 'No Solution'
656
657# Driver Function
658print(17, '->', hampath(17))
659print(20, '->', hampath(20))
660print(25, '->', hampath(25))
661
662Output:
663
66417 -> [16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8, 17]
66520 -> No Solution
66625 -> [2, 23, 13, 12, 24, 25, 11, 14, 22, 3, 1, 8, 17, 19, 6, 10,
667 15, 21, 4, 5, 20, 16, 9, 7, 18]
668________________________________________________________________________________________________________________________________________________________________________________________________________________
669This problem can be solved with Dijkstra's algorithm. Let's denote the state as , where is the number of shopping centers and is a bitmask of the first bits denoting the kinds of fish which have already been bought.
670
671The starting state is (1, 0), meaning we start at shopping center 1 and have not yet purchased any fish. The shortest distance to the state denotes the minimum time required to visit shopping center with fish from the mask bought.
672
673While spreading from the current state, there are two possible options:
674
675 To state with the time where . Recall that buying any amount of fish doesn't take any time, so it is always optimal to buy all fish sold in the shopping centers. This transition corresponds to buying the fish.
676
677 To state where is adjacent to with the time , and is the time required to pass the road from to . This transition corresponds to moving by a road.
678
679When all the minimal times are calculated, let's brute-force the mask of the fish that will be bought by Little Cat and mask of the fish that will be bought by Big Cat. The essential condition is or . Then, the minimal time for this configuration will simply be equal to . Among all these configurations, choose the best one (i.e., the one having the minimal answer).
680
681 Set by zxqfd555
682
683Problem Setter's code:
684
685#include <cassert>
686#include <cstdio>
687#include <algorithm>
688#include <iostream>
689#include <set>
690#include <vector>
691
692using namespace std;
693
694const int INF = 1000000000;
695const int MAX_NODES = 1000 + 10;
696const int MAX_MASK = 1024 + 10;
697
698int dist[MAX_NODES][MAX_MASK], n, m, k, cti, a[MAX_NODES], x, y, z;
699set<pair<int, pair<int, int> > > S;
700vector<pair<int, int> > adj[MAX_NODES];
701bool occurs[MAX_NODES];
702
703inline void push (int vn, int vm, int vv) {
704 if (dist[vn][vm] <= vv)
705 return ;
706 pair<int, pair<int, int> > mp = make_pair(dist[vn][vm], make_pair(vn, vm));
707 if (S.find(mp) != S.end())
708 S.erase(S.find(mp));
709 dist[vn][vm] = vv;
710 mp.first = vv;
711 S.insert(mp);
712}
713
714int main () {
715// freopen("input.txt", "r", stdin);
716// freopen("output.txt", "w", stdout);
717 ios_base::sync_with_stdio(false);
718 cin >> n >> m >> k;
719 assert(2 <= n && n <= 1000);
720 assert(1 <= m && m <= 2000);
721 assert(1 <= k && k <= 10);
722 for(int i = 1; i <= n; i++) {
723 cin >> cti;
724 assert(0 <= cti && cti <= k);
725 for(int j = 1; j <= cti; j++) {
726 cin >> x;
727 assert(1 <= x && x <= k);
728 assert((a[i] & (1 << (x - 1))) == 0);
729 a[i] |= (1 << (x - 1));
730 }
731 }
732 set<pair<int, int> > edges;
733 for(int i = 1; i <= m; i++) {
734 cin >> x >> y >> z;
735 assert(1 <= x && x <= n);
736 assert(1 <= y && y <= n);
737 assert(1 <= z && z <= 10000);
738 assert(x != y);
739 edges.insert(make_pair(min(x, y), max(x, y)));
740 adj[x].push_back(make_pair(y, z));
741 adj[y].push_back(make_pair(x, z));
742 }
743 assert(edges.size() == m);
744 for(int i = 1; i <= n; i++)
745 for(int j = 0; j < (1 << k); j++)
746 dist[i][j] = INF;
747 push(1, a[1], 0);
748 while (S.size() > 0) {
749 int vn = S.begin()->second.first;
750 int vm = S.begin()->second.second;
751 occurs[vn] = true;
752 S.erase(S.begin());
753 for(int i = 0; i < adj[vn].size(); i++)
754 push(adj[vn][i].first, vm | a[adj[vn][i].first], dist[vn][vm] + adj[vn][i].second);
755 }
756 for(int i = 1; i <= n; i++)
757 assert(occurs[i]);
758 int ret = INF;
759 for(int i = 0; i < (1 << k); i++)
760 for(int j = i; j < (1 << k); j++) if ((i | j) == ((1 << k) - 1))
761 ret = min(ret, max(dist[n][i], dist[n][j]));
762 cout << ret << endl;
763 return 0;
764}
765
766 Tested by shef_2318
767
768Problem Tester's code:
769
770#include <bits/stdc++.h>
771
772using namespace std;
773
774#define X first
775#define Y second
776#define mp make_pair
777
778const int MAX_MASK = 1024, MAXN = 1010, INF = 1E9;
779int n, m, k;
780int d[MAXN][MAX_MASK], msk[MAXN];
781vector< pair<int, int> > go[MAXN];
782set< pair<int, pair<int, int> > > s;
783
784int main() {
785 scanf("%d%d%d", &n, &m, &k);
786 for (int i = 1; i <= n; i++) {
787 int t;
788 scanf("%d", &t);
789 for (int j = 0; j < t; j++) {
790 int x;
791 scanf("%d", &x);
792 x--;
793 msk[i] |= (1<<x);
794 }
795 }
796 for (int i = 0; i < m; i++) {
797 int aa, bb, cc;
798 scanf("%d%d%d", &aa, &bb, &cc);
799 assert(1 <= aa && aa <= n);
800 assert(1 <= bb && bb <= n);
801 assert(aa != bb);
802 go[aa].push_back( mp(bb, cc) );
803 go[bb].push_back( mp(aa, cc) );
804 }
805 for (int i = 1; i <= n; i++) {
806 for (int j = 0; j < MAX_MASK; j++) {
807 d[i][j] = INF;
808 }
809 }
810 d[1][ msk[1] ] = 0;
811 s.insert( mp(0, mp(1, msk[1]) ) );
812 while (!s.empty() ) {
813 pair<int, pair<int, int> > cur = *s.begin();
814 s.erase(s.begin() );
815 int v = cur.Y.X, curmsk = cur.Y.Y, curd = cur.X;
816 for (int j = 0; j < go[v].size(); j++) {
817 int to = go[v][j].X;
818 int cost = go[v][j].Y;
819 int tomsk = curmsk | msk[to];
820 if (d[to][tomsk] > curd + cost) {
821 s.erase( mp(d[to][tomsk], mp(to, tomsk) ) );
822 d[to][tomsk] = curd + cost;
823 s.insert( mp(d[to][tomsk], mp(to, tomsk) ) );
824 }
825 }
826 }
827 int ans = INF;
828 for (int i = 0; i < (1<<k); i++) {
829 for (int j = 0; j < (1<<k); j++) {
830 if ( (i | j) == ( (1<<k) - 1 ) ) {
831 ans = min(ans, max(d[n][i], d[n][j]) );
832 }
833 }
834 }
835 if (ans == INF) {
836 assert(false);
837 }
838 cout<<ans<<endl;
839 return 0;
840}
841
842________________________________________________________________________________________________________________________________________________________________________________________________________________
843
844Input : [[0, 1, 0, 0, 1],
845 [1, 0, 1, 1, 0],
846 [0, 1, 0, 1, 0],
847 [0, 1, 1, 0, 0],
848 [1, 0, 0, 0, 0]]
849
850Output : 5 -> 1 -> 2 -> 4 -> 3 -> 2
851
852Input : [[0, 1, 0, 1, 1],
853 [1, 0, 1, 0, 1],
854 [0, 1, 0, 1, 1],
855 [1, 1, 1, 0, 0],
856 [1, 0, 1, 0, 0]]
857
858Output : "No Solution"
859
860
861// A C++ program print Eulerian Trail in a
862// given Eulerian or Semi-Eulerian Graph
863#include <iostream>
864#include <string.h>
865#include <algorithm>
866#include <list>
867using namespace std;
868
869// A class that represents an undirected graph
870class Graph
871{
872// No. of vertices
873 int V;
874
875 // A dynamic array of adjacency lists
876 list<int> *adj;
877public:
878
879 // Constructor and destructor
880 Graph(int V)
881 {
882 this->V = V;
883 adj = new list<int>[V];
884 }
885 ~Graph()
886 {
887 delete [] adj;
888 }
889
890 // functions to add and remove edge
891 void addEdge(int u, int v)
892 {
893 adj[u].push_back(v);
894 adj[v].push_back(u);
895 }
896
897 void rmvEdge(int u, int v);
898
899 // Methods to print Eulerian tour
900 void printEulerTour();
901 void printEulerUtil(int s);
902
903 // This function returns count of vertices
904 // reachable from v. It does DFS
905 int DFSCount(int v, bool visited[]);
906
907 // Utility function to check if edge u-v
908 // is a valid next edge in Eulerian trail or circuit
909 bool isValidNextEdge(int u, int v);
910};
911
912/* The main function that print Eulerian Trail.
913It first finds an odd degree vertex (if there is any)
914and then calls printEulerUtil() to print the path */
915void Graph::printEulerTour()
916{
917 // Find a vertex with odd degree
918 int u = 0;
919
920 for (int i = 0; i < V; i++)
921 if (adj[i].size() & 1)
922 {
923 u = i;
924 break;
925 }
926
927 // Print tour starting from oddv
928 printEulerUtil(u);
929 cout << endl;
930}
931
932// Print Euler tour starting from vertex u
933void Graph::printEulerUtil(int u)
934{
935
936 // Recur for all the vertices adjacent to
937 // this vertex
938 list<int>::iterator i;
939 for (i = adj[u].begin(); i != adj[u].end(); ++i)
940 {
941 int v = *i;
942
943 // If edge u-v is not removed and it's a a
944 // valid next edge
945 if (v != -1 && isValidNextEdge(u, v))
946 {
947 cout << u << "-" << v << " ";
948 rmvEdge(u, v);
949 printEulerUtil(v);
950 }
951 }
952}
953
954// The function to check if edge u-v can be considered
955// as next edge in Euler Tout
956bool Graph::isValidNextEdge(int u, int v)
957{
958
959 // The edge u-v is valid in one of the following
960 // two cases:
961
962 // 1) If v is the only adjacent vertex of u
963 int count = 0; // To store count of adjacent vertices
964 list<int>::iterator i;
965 for (i = adj[u].begin(); i != adj[u].end(); ++i)
966 if (*i != -1)
967 count++;
968 if (count == 1)
969 return true;
970
971
972 // 2) If there are multiple adjacents, then u-v
973 // is not a bridge
974 // Do following steps to check if u-v is a bridge
975
976 // 2.a) count of vertices reachable from u
977 bool visited[V];
978 memset(visited, false, V);
979 int count1 = DFSCount(u, visited);
980
981 // 2.b) Remove edge (u, v) and after removing
982 // the edge, count vertices reachable from u
983 rmvEdge(u, v);
984 memset(visited, false, V);
985 int count2 = DFSCount(u, visited);
986
987 // 2.c) Add the edge back to the graph
988 addEdge(u, v);
989
990 // 2.d) If count1 is greater, then edge (u, v)
991 // is a bridge
992 return (count1 > count2)? false: true;
993}
994
995// This function removes edge u-v from graph.
996// It removes the edge by replacing adjcent
997// vertex value with -1.
998void Graph::rmvEdge(int u, int v)
999{
1000 // Find v in adjacency list of u and replace
1001 // it with -1
1002 list<int>::iterator iv = find(adj[u].begin(),
1003 adj[u].end(), v);
1004 *iv = -1;
1005
1006
1007 // Find u in adjacency list of v and replace
1008 // it with -1
1009 list<int>::iterator iu = find(adj[v].begin(),
1010 adj[v].end(), u);
1011 *iu = -1;
1012}
1013
1014// A DFS based function to count reachable
1015// vertices from v
1016int Graph::DFSCount(int v, bool visited[])
1017{
1018 // Mark the current node as visited
1019 visited[v] = true;
1020 int count = 1;
1021
1022 // Recur for all vertices adjacent to this vertex
1023 list<int>::iterator i;
1024 for (i = adj[v].begin(); i != adj[v].end(); ++i)
1025 if (*i != -1 && !visited[*i])
1026 count += DFSCount(*i, visited);
1027
1028 return count;
1029}
1030
1031// Driver program to test above function
1032int main()
1033{
1034 // Let us first create and test
1035 // graphs shown in above figure
1036 Graph g1(4);
1037 g1.addEdge(0, 1);
1038 g1.addEdge(0, 2);
1039 g1.addEdge(1, 2);
1040 g1.addEdge(2, 3);
1041 g1.printEulerTour();
1042
1043 Graph g3(4);
1044 g3.addEdge(0, 1);
1045 g3.addEdge(1, 0);
1046 g3.addEdge(0, 2);
1047 g3.addEdge(2, 0);
1048 g3.addEdge(2, 3);
1049 g3.addEdge(3, 1);
1050
1051 // comment out this line and you will see that
1052 // it gives TLE because there is no possible
1053 // output g3.addEdge(0, 3);
1054 g3.printEulerTour();
1055
1056 return 0;
1057}
1058Output:
1059
10602-0 0-1 1-2 2-3
10611-0 0-2 2-3 3-1 1-0 0-2
1062
1063________________________________________________________________________________________________________________________________________________________________________________________________________________
1064Output should be
1065Vertex Distance Path
10660 -> 1 4 0 1
10670 -> 2 12 0 1 2
10680 -> 3 19 0 1 2 3
10690 -> 4 21 0 7 6 5 4
10700 -> 5 11 0 7 6 5
10710 -> 6 9 0 7 6
10720 -> 7 8 0 7
10730 -> 8 14 0 1 2 8
1074
1075The idea is to create a separate array parent[]. Value of parent[v] for a vertex v stores parent vertex of v in shortest path tree. Parent of root (or source vertex) is -1. Whenever we find shorter path through a vertex u, we make u as parent of current vertex.
1076
1077Once we have parent array constructed, we can print path using below recursive function.
1078
1079void printPath(int parent[], int j)
1080{
1081 // Base Case : If j is source
1082 if (parent[j]==-1)
1083 return;
1084
1085 printPath(parent, parent[j]);
1086
1087 printf("%d ", j);
1088}
1089
1090Below is the complete implementation
1091
1092// A C / C++ program for Dijkstra's single source shortest
1093// path algorithm. The program is for adjacency matrix
1094// representation of the graph.
1095#include <stdio.h>
1096#include <limits.h>
1097
1098// Number of vertices in the graph
1099#define V 9
1100
1101// A utility function to find the vertex with minimum distance
1102// value, from the set of vertices not yet included in shortest
1103// path tree
1104int minDistance(int dist[], bool sptSet[])
1105{
1106 // Initialize min value
1107 int min = INT_MAX, min_index;
1108
1109 for (int v = 0; v < V; v++)
1110 if (sptSet[v] == false && dist[v] <= min)
1111 min = dist[v], min_index = v;
1112
1113 return min_index;
1114}
1115
1116// Function to print shortest path from source to j
1117// using parent array
1118void printPath(int parent[], int j)
1119{
1120 // Base Case : If j is source
1121 if (parent[j]==-1)
1122 return;
1123
1124 printPath(parent, parent[j]);
1125
1126 printf("%d ", j);
1127}
1128
1129// A utility function to print the constructed distance
1130// array
1131int printSolution(int dist[], int n, int parent[])
1132{
1133 int src = 0;
1134 printf("Vertex\t Distance\tPath");
1135 for (int i = 1; i < V; i++)
1136 {
1137 printf("\n%d -> %d \t\t %d\t\t%d ", src, i, dist[i], src);
1138 printPath(parent, i);
1139 }
1140}
1141
1142// Funtion that implements Dijkstra's single source shortest path
1143// algorithm for a graph represented using adjacency matrix
1144// representation
1145void dijkstra(int graph[V][V], int src)
1146{
1147 int dist[V]; // The output array. dist[i] will hold
1148 // the shortest distance from src to i
1149
1150 // sptSet[i] will true if vertex i is included / in shortest
1151 // path tree or shortest distance from src to i is finalized
1152 bool sptSet[V];
1153
1154 // Parent array to store shortest path tree
1155 int parent[V];
1156
1157 // Initialize all distances as INFINITE and stpSet[] as false
1158 for (int i = 0; i < V; i++)
1159 {
1160 parent[0] = -1;
1161 dist[i] = INT_MAX;
1162 sptSet[i] = false;
1163 }
1164
1165 // Distance of source vertex from itself is always 0
1166 dist[src] = 0;
1167
1168 // Find shortest path for all vertices
1169 for (int count = 0; count < V-1; count++)
1170 {
1171 // Pick the minimum distance vertex from the set of
1172 // vertices not yet processed. u is always equal to src
1173 // in first iteration.
1174 int u = minDistance(dist, sptSet);
1175
1176 // Mark the picked vertex as processed
1177 sptSet[u] = true;
1178
1179 // Update dist value of the adjacent vertices of the
1180 // picked vertex.
1181 for (int v = 0; v < V; v++)
1182
1183 // Update dist[v] only if is not in sptSet, there is
1184 // an edge from u to v, and total weight of path from
1185 // src to v through u is smaller than current value of
1186 // dist[v]
1187 if (!sptSet[v] && graph[u][v] &&
1188 dist[u] + graph[u][v] < dist[v])
1189 {
1190 parent[v] = u;
1191 dist[v] = dist[u] + graph[u][v];
1192 }
1193 }
1194
1195 // print the constructed distance array
1196 printSolution(dist, V, parent);
1197}
1198
1199// driver program to test above function
1200int main()
1201{
1202 /* Let us create the example graph discussed above */
1203 int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
1204 {4, 0, 8, 0, 0, 0, 0, 11, 0},
1205 {0, 8, 0, 7, 0, 4, 0, 0, 2},
1206 {0, 0, 7, 0, 9, 14, 0, 0, 0},
1207 {0, 0, 0, 9, 0, 10, 0, 0, 0},
1208 {0, 0, 4, 0, 10, 0, 2, 0, 0},
1209 {0, 0, 0, 14, 0, 2, 0, 1, 6},
1210 {8, 11, 0, 0, 0, 0, 1, 0, 7},
1211 {0, 0, 2, 0, 0, 0, 6, 7, 0}
1212 };
1213
1214 dijkstra(graph, 0);
1215
1216 return 0;
1217}
1218
1219Output:
1220
1221Vertex Distance Path
12220 -> 1 4 0 1
12230 -> 2 12 0 1 2
12240 -> 3 19 0 1 2 3
12250 -> 4 21 0 7 6 5 4
12260 -> 5 11 0 7 6 5
12270 -> 6 9 0 7 6
12280 -> 7 8 0 7
12290 -> 8 14 0 1 2 8
1230________________________________________________________________________________________________________________________________________________________________________________________________________________
1231Input : 1033 8179
1232Output :6
1233
1234Input : 1373 8017
1235Output : 7
1236
1237Input : 1033 1033
1238Output : 0
1239
1240Recommended: Please try your approach on {IDE} first, before moving on to the solution.
1241
1242
1243The question can be solved by BFS and it is a pretty interesting to solve as a starting problem for beginners. We first find out all 4 digit prime numbers till 9999 using technique of Sieve of Eratosthenes. And then using those numbers formed the graph using adjacency list. After forming the adjacency list, we used simple BFS to solve the problem.
1244// CPP program to reach a prime number from another
1245// by changing single digits and using only prime
1246// numbers.
1247#include <bits/stdc++.h>
1248using namespace std;
1249
1250class graph {
1251 int V;
1252 list<int>* l;
1253public:
1254 graph(int V)
1255 {
1256 this->V = V;
1257 l = new list<int>[V];
1258 }
1259 void addedge(int V1, int V2)
1260 {
1261 l[V1].push_back(V2);
1262 l[V2].push_back(V1);
1263 }
1264 int bfs(int in1, int in2);
1265};
1266
1267// Finding all 4 digit prime numbers
1268void SieveOfEratosthenes(vector<int>& v)
1269{
1270 // Create a boolean array "prime[0..n]" and initialize
1271 // all entries it as true. A value in prime[i] will
1272 // finally be false if i is Not a prime, else true.
1273 int n = 9999;
1274 bool prime[n + 1];
1275 memset(prime, true, sizeof(prime));
1276
1277 for (int p = 2; p * p <= n; p++) {
1278
1279 // If prime[p] is not changed, then it is a prime
1280 if (prime[p] == true) {
1281
1282 // Update all multiples of p
1283 for (int i = p * p; i <= n; i += p)
1284 prime[i] = false;
1285 }
1286 }
1287
1288 // Forming a vector of prime numbers
1289 for (int p = 1000; p <= n; p++)
1290 if (prime[p])
1291 v.push_back(p);
1292
1293 // cout<<v.size();
1294}
1295
1296// in1 and in2 are two vertices of graph which are
1297// actually indexes in pset[]
1298int graph::bfs(int in1, int in2)
1299{
1300 int visited[V];
1301 memset(visited, 0, sizeof(visited));
1302 queue<int> que;
1303 visited[in1] = 1;
1304 que.push(in1);
1305 list<int>::iterator i;
1306 int f = 0;
1307 while (!que.empty()) {
1308 int p = que.front();
1309 que.pop();
1310 for (i = l[p].begin(); i != l[p].end(); i++) {
1311 if (!visited[*i]) {
1312 visited[*i] = visited[p] + 1;
1313 que.push(*i);
1314 }
1315 if (*i == in2) {
1316 return visited[*i] - 1;
1317 }
1318 }
1319 }
1320}
1321
1322// Returns true if num1 and num2 differ by single
1323// digit.
1324bool compare(int num1, int num2)
1325{
1326 // To compare the digits
1327 string s1 = to_string(num1);
1328 string s2 = to_string(num2);
1329 int c = 0;
1330 if (s1[0] != s2[0])
1331 c++;
1332 if (s1[1] != s2[1])
1333 c++;
1334 if (s1[2] != s2[2])
1335 c++;
1336 if (s1[3] != s2[3])
1337 c++;
1338
1339 // If the numbers differ only by a single
1340 // digit return true else false
1341 return (c == 1);
1342}
1343
1344int shortestPath(int num1, int num2)
1345{
1346 // Generate all 4 digit
1347 vector<int> pset;
1348 SieveOfEratosthenes(pset);
1349
1350
1351 // Create a graph where node numbers are indexes
1352 // in pset[] and there is an edge between two
1353 // nodes only if they differ by single digit.
1354 graph g(pset.size());
1355 for (int i = 0; i < pset.size(); i++)
1356 for (int j = i + 1; j < pset.size(); j++)
1357 if (compare(pset[i], pset[j]))
1358 g.addedge(i, j);
1359
1360
1361 // Since graph nodes represent indexes of numbers
1362 // in pset[], we find indexes of num1 and num2.
1363 int in1, in2;
1364 for (int j = 0; j < pset.size(); j++)
1365 if (pset[j] == num1)
1366 in1 = j;
1367 for (int j = 0; j < pset.size(); j++)
1368 if (pset[j] == num2)
1369 in2 = j;
1370
1371 return g.bfs(in1, in2);
1372}
1373
1374// Driver code
1375int main()
1376{
1377 int num1 = 1033, num2 = 8179;
1378 cout << shortestPath(num1, num2);
1379 return 0;
1380}
1381
1382Output :
1383
13846
1385________________________________________________________________________________________________________________________________________________________________________________________________________________
1386Following is the basic Greedy Algorithm to assign colors. It doesn’t guarantee to use minimum colors, but it guarantees an upper bound on the number of colors. The basic algorithm never uses more than d+1 colors where d is the maximum degree of a vertex in the given graph.
1387
1388Basic Greedy Coloring Algorithm:
1389
1390 1. Color first vertex with first color.
1391 2. Do following for remaining V-1 vertices.
1392 ….. a) Consider the currently picked vertex and color it with the
1393 lowest numbered color that has not been used on any previously
1394 colored vertices adjacent to it. If all previously used colors
1395 appear on vertices adjacent to v, assign a new color to it.
1396
1397Following are C++ and Java implementations of the above Greedy Algorithm.
1398
1399// A C++ program to implement greedy algorithm for graph coloring
1400#include <iostream>
1401#include <list>
1402using namespace std;
1403
1404// A class that represents an undirected graph
1405class Graph
1406{
1407 int V; // No. of vertices
1408 list<int> *adj; // A dynamic array of adjacency lists
1409public:
1410 // Constructor and destructor
1411 Graph(int V) { this->V = V; adj = new list<int>[V]; }
1412 ~Graph() { delete [] adj; }
1413
1414 // function to add an edge to graph
1415 void addEdge(int v, int w);
1416
1417 // Prints greedy coloring of the vertices
1418 void greedyColoring();
1419};
1420
1421void Graph::addEdge(int v, int w)
1422{
1423 adj[v].push_back(w);
1424 adj[w].push_back(v); // Note: the graph is undirected
1425}
1426
1427// Assigns colors (starting from 0) to all vertices and prints
1428// the assignment of colors
1429void Graph::greedyColoring()
1430{
1431 int result[V];
1432
1433 // Assign the first color to first vertex
1434 result[0] = 0;
1435
1436 // Initialize remaining V-1 vertices as unassigned
1437 for (int u = 1; u < V; u++)
1438 result[u] = -1; // no color is assigned to u
1439
1440 // A temporary array to store the available colors. True
1441 // value of available[cr] would mean that the color cr is
1442 // assigned to one of its adjacent vertices
1443 bool available[V];
1444 for (int cr = 0; cr < V; cr++)
1445 available[cr] = false;
1446
1447 // Assign colors to remaining V-1 vertices
1448 for (int u = 1; u < V; u++)
1449 {
1450 // Process all adjacent vertices and flag their colors
1451 // as unavailable
1452 list<int>::iterator i;
1453 for (i = adj[u].begin(); i != adj[u].end(); ++i)
1454 if (result[*i] != -1)
1455 available[result[*i]] = true;
1456
1457 // Find the first available color
1458 int cr;
1459 for (cr = 0; cr < V; cr++)
1460 if (available[cr] == false)
1461 break;
1462
1463 result[u] = cr; // Assign the found color
1464
1465 // Reset the values back to false for the next iteration
1466 for (i = adj[u].begin(); i != adj[u].end(); ++i)
1467 if (result[*i] != -1)
1468 available[result[*i]] = false;
1469 }
1470
1471 // print the result
1472 for (int u = 0; u < V; u++)
1473 cout << "Vertex " << u << " ---> Color "
1474 << result[u] << endl;
1475}
1476
1477// Driver program to test above function
1478int main()
1479{
1480 Graph g1(5);
1481 g1.addEdge(0, 1);
1482 g1.addEdge(0, 2);
1483 g1.addEdge(1, 2);
1484 g1.addEdge(1, 3);
1485 g1.addEdge(2, 3);
1486 g1.addEdge(3, 4);
1487 cout << "Coloring of graph 1 \n";
1488 g1.greedyColoring();
1489
1490 Graph g2(5);
1491 g2.addEdge(0, 1);
1492 g2.addEdge(0, 2);
1493 g2.addEdge(1, 2);
1494 g2.addEdge(1, 4);
1495 g2.addEdge(2, 4);
1496 g2.addEdge(4, 3);
1497 cout << "\nColoring of graph 2 \n";
1498 g2.greedyColoring();
1499
1500 return 0;
1501}
1502
1503Output:
1504
1505
1506
1507Coloring of graph 1
1508Vertex 0 ---> Color 0
1509Vertex 1 ---> Color 1
1510Vertex 2 ---> Color 2
1511Vertex 3 ---> Color 0
1512Vertex 4 ---> Color 1
1513
1514Coloring of graph 2
1515Vertex 0 ---> Color 0
1516Vertex 1 ---> Color 1
1517Vertex 2 ---> Color 2
1518Vertex 3 ---> Color 0
1519Vertex 4 ---> Color 3
1520
1521Time Complexity: O(V^2 + E) in worst case.
1522
1523________________________________________________________________________________________________________________________________________________________________________________________________________________
1524
1525Shortest Path in Directed Acyclic Graph
1526
1527Given a Weighted Directed Acyclic Graph and a source vertex in the graph, find the shortest paths from given source to all other vertices.
1528
1529For a general weighted graph, we can calculate single source shortest distances in O(VE) time using Bellman–Ford Algorithm. For a graph with no negative weights, we can do better and calculate single source shortest distances in O(E + VLogV) time using Dijkstra’s algorithm. Can we do even better for Directed Acyclic Graph (DAG)? We can calculate single source shortest distances in O(V+E) time for DAGs. The idea is to use Topological Sorting.
1530
1531We initialize distances to all vertices as infinite and distance to source as 0, then we find a topological sorting of the graph. Topological Sorting of a graph represents a linear ordering of the graph (See below, figure (b) is a linear representation of figure (a) ). Once we have topological order (or linear representation), we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent using distance of current vertex.
1532
1533Following is complete algorithm for finding shortest distances.
15341) Initialize dist[] = {INF, INF, ….} and dist[s] = 0 where s is the source vertex.
15352) Create a toplogical order of all vertices.
15363) Do following for every vertex u in topological order.
1537………..Do following for every adjacent vertex v of u
1538………………if (dist[v] > dist[u] + weight(u, v))
1539………………………dist[v] = dist[u] + weight(u, v)
1540
1541// C++ program to find single source shortest paths for Directed Acyclic Graphs
1542#include<iostream>
1543#include <list>
1544#include <stack>
1545#include <limits.h>
1546#define INF INT_MAX
1547using namespace std;
1548
1549// Graph is represented using adjacency list. Every node of adjacency list
1550// contains vertex number of the vertex to which edge connects. It also
1551// contains weight of the edge
1552class AdjListNode
1553{
1554 int v;
1555 int weight;
1556public:
1557 AdjListNode(int _v, int _w) { v = _v; weight = _w;}
1558 int getV() { return v; }
1559 int getWeight() { return weight; }
1560};
1561
1562// Class to represent a graph using adjacency list representation
1563class Graph
1564{
1565 int V; // No. of vertices'
1566
1567 // Pointer to an array containing adjacency lists
1568 list<AdjListNode> *adj;
1569
1570 // A function used by shortestPath
1571 void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
1572public:
1573 Graph(int V); // Constructor
1574
1575 // function to add an edge to graph
1576 void addEdge(int u, int v, int weight);
1577
1578 // Finds shortest paths from given source vertex
1579 void shortestPath(int s);
1580};
1581
1582Graph::Graph(int V)
1583{
1584 this->V = V;
1585 adj = new list<AdjListNode>[V];
1586}
1587
1588void Graph::addEdge(int u, int v, int weight)
1589{
1590 AdjListNode node(v, weight);
1591 adj[u].push_back(node); // Add v to u's list
1592}
1593
1594// A recursive function used by shortestPath. See below link for details
1595// https://www.geeksforgeeks.org/topological-sorting/
1596void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)
1597{
1598 // Mark the current node as visited
1599 visited[v] = true;
1600
1601 // Recur for all the vertices adjacent to this vertex
1602 list<AdjListNode>::iterator i;
1603 for (i = adj[v].begin(); i != adj[v].end(); ++i)
1604 {
1605 AdjListNode node = *i;
1606 if (!visited[node.getV()])
1607 topologicalSortUtil(node.getV(), visited, Stack);
1608 }
1609
1610 // Push current vertex to stack which stores topological sort
1611 Stack.push(v);
1612}
1613
1614// The function to find shortest paths from given vertex. It uses recursive
1615// topologicalSortUtil() to get topological sorting of given graph.
1616void Graph::shortestPath(int s)
1617{
1618 stack<int> Stack;
1619 int dist[V];
1620
1621 // Mark all the vertices as not visited
1622 bool *visited = new bool[V];
1623 for (int i = 0; i < V; i++)
1624 visited[i] = false;
1625
1626 // Call the recursive helper function to store Topological Sort
1627 // starting from all vertices one by one
1628 for (int i = 0; i < V; i++)
1629 if (visited[i] == false)
1630 topologicalSortUtil(i, visited, Stack);
1631
1632 // Initialize distances to all vertices as infinite and distance
1633 // to source as 0
1634 for (int i = 0; i < V; i++)
1635 dist[i] = INF;
1636 dist[s] = 0;
1637
1638 // Process vertices in topological order
1639 while (Stack.empty() == false)
1640 {
1641 // Get the next vertex from topological order
1642 int u = Stack.top();
1643 Stack.pop();
1644
1645 // Update distances of all adjacent vertices
1646 list<AdjListNode>::iterator i;
1647 if (dist[u] != INF)
1648 {
1649 for (i = adj[u].begin(); i != adj[u].end(); ++i)
1650 if (dist[i->getV()] > dist[u] + i->getWeight())
1651 dist[i->getV()] = dist[u] + i->getWeight();
1652 }
1653 }
1654
1655 // Print the calculated shortest distances
1656 for (int i = 0; i < V; i++)
1657 (dist[i] == INF)? cout << "INF ": cout << dist[i] << " ";
1658}
1659
1660// Driver program to test above functions
1661int main()
1662{
1663 // Create a graph given in the above diagram. Here vertex numbers are
1664 // 0, 1, 2, 3, 4, 5 with following mappings:
1665 // 0=r, 1=s, 2=t, 3=x, 4=y, 5=z
1666 Graph g(6);
1667 g.addEdge(0, 1, 5);
1668 g.addEdge(0, 2, 3);
1669 g.addEdge(1, 3, 6);
1670 g.addEdge(1, 2, 2);
1671 g.addEdge(2, 4, 4);
1672 g.addEdge(2, 5, 2);
1673 g.addEdge(2, 3, 7);
1674 g.addEdge(3, 4, -1);
1675 g.addEdge(4, 5, -2);
1676
1677 int s = 1;
1678 cout << "Following are shortest distances from source " << s <<" n";
1679 g.shortestPath(s);
1680
1681 return 0;
1682}
1683
1684Output:
1685
1686Following are shortest distances from source 1
1687INF 0 2 6 5 3
1688
1689Time Complexity: Time complexity of topological sorting is O(V+E). After finding topological order, the algorithm process all vertices and for every vertex, it runs a loop for all adjacent vertices. Total adjacent vertices in a graph is O(E). So the inner loop runs O(V+E) times. Therefore, overall time complexity of this algorithm is O(V+E).
1690________________________________________________________________________________________________________________________________________________________________________________________________________________
1691
1692Relation (Similarity and Differences) with other algorithms-
1693Dijkstra is a special case of A* Search Algorithm, where h = 0 for all nodes.
1694
1695Implementation
1696We can use any data structure to implement open list and closed list but for best performance we use a set< > data structure of C++ STL(implemented as Red-Black Tree) and a boolean hash table for a closed list.
1697
1698The implementations are similar to Dijsktra’s algorithm. If we use a Fibonacci heap to implement the open list instead of a binary heap/self-balancing tree, then the performance will become better (as Fibonacci heap takes O(1) average time to insert into open list and to decrease key)
1699
1700Also to reduce the time taken to calculate g, we will use dynamic programming.
1701// A C++ Program to implement A* Search Algorithm
1702#include<bits/stdc++.h>
1703using namespace std;
1704
1705#define ROW 9
1706#define COL 10
1707
1708// Creating a shortcut for int, int pair type
1709typedef pair<int, int> Pair;
1710
1711// Creating a shortcut for pair<int, pair<int, int>> type
1712typedef pair<double, pair<int, int>> pPair;
1713
1714// A structure to hold the neccesary parameters
1715struct cell
1716{
1717 // Row and Column index of its parent
1718 // Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
1719 int parent_i, parent_j;
1720 // f = g + h
1721 double f, g, h;
1722};
1723
1724// A Utility Function to check whether given cell (row, col)
1725// is a valid cell or not.
1726bool isValid(int row, int col)
1727{
1728 // Returns true if row number and column number
1729 // is in range
1730 return (row >= 0) && (row < ROW) &&
1731 (col >= 0) && (col < COL);
1732}
1733
1734// A Utility Function to check whether the given cell is
1735// blocked or not
1736bool isUnBlocked(int grid[][COL], int row, int col)
1737{
1738 // Returns true if the cell is not blocked else false
1739 if (grid[row][col] == 1)
1740 return (true);
1741 else
1742 return (false);
1743}
1744
1745// A Utility Function to check whether destination cell has
1746// been reached or not
1747bool isDestination(int row, int col, Pair dest)
1748{
1749 if (row == dest.first && col == dest.second)
1750 return (true);
1751 else
1752 return (false);
1753}
1754
1755// A Utility Function to calculate the 'h' heuristics.
1756double calculateHValue(int row, int col, Pair dest)
1757{
1758 // Return using the distance formula
1759 return ((double)sqrt ((row-dest.first)*(row-dest.first)
1760 + (col-dest.second)*(col-dest.second)));
1761}
1762
1763// A Utility Function to trace the path from the source
1764// to destination
1765void tracePath(cell cellDetails[][COL], Pair dest)
1766{
1767 printf ("\nThe Path is ");
1768 int row = dest.first;
1769 int col = dest.second;
1770
1771 stack<Pair> Path;
1772
1773 while (!(cellDetails[row][col].parent_i == row
1774 && cellDetails[row][col].parent_j == col ))
1775 {
1776 Path.push (make_pair (row, col));
1777 int temp_row = cellDetails[row][col].parent_i;
1778 int temp_col = cellDetails[row][col].parent_j;
1779 row = temp_row;
1780 col = temp_col;
1781 }
1782
1783 Path.push (make_pair (row, col));
1784 while (!Path.empty())
1785 {
1786 pair<int,int> p = Path.top();
1787 Path.pop();
1788 printf("-> (%d,%d) ",p.first,p.second);
1789 }
1790
1791 return;
1792}
1793
1794// A Function to find the shortest path between
1795// a given source cell to a destination cell according
1796// to A* Search Algorithm
1797void aStarSearch(int grid[][COL], Pair src, Pair dest)
1798{
1799 // If the source is out of range
1800 if (isValid (src.first, src.second) == false)
1801 {
1802 printf ("Source is invalid\n");
1803 return;
1804 }
1805
1806 // If the destination is out of range
1807 if (isValid (dest.first, dest.second) == false)
1808 {
1809 printf ("Destination is invalid\n");
1810 return;
1811 }
1812
1813 // Either the source or the destination is blocked
1814 if (isUnBlocked(grid, src.first, src.second) == false ||
1815 isUnBlocked(grid, dest.first, dest.second) == false)
1816 {
1817 printf ("Source or the destination is blocked\n");
1818 return;
1819 }
1820
1821 // If the destination cell is the same as source cell
1822 if (isDestination(src.first, src.second, dest) == true)
1823 {
1824 printf ("We are already at the destination\n");
1825 return;
1826 }
1827
1828 // Create a closed list and initialise it to false which means
1829 // that no cell has been included yet
1830 // This closed list is implemented as a boolean 2D array
1831 bool closedList[ROW][COL];
1832 memset(closedList, false, sizeof (closedList));
1833
1834 // Declare a 2D array of structure to hold the details
1835 //of that cell
1836 cell cellDetails[ROW][COL];
1837
1838 int i, j;
1839
1840 for (i=0; i<ROW; i++)
1841 {
1842 for (j=0; j<COL; j++)
1843 {
1844 cellDetails[i][j].f = FLT_MAX;
1845 cellDetails[i][j].g = FLT_MAX;
1846 cellDetails[i][j].h = FLT_MAX;
1847 cellDetails[i][j].parent_i = -1;
1848 cellDetails[i][j].parent_j = -1;
1849 }
1850 }
1851
1852 // Initialising the parameters of the starting node
1853 i = src.first, j = src.second;
1854 cellDetails[i][j].f = 0.0;
1855 cellDetails[i][j].g = 0.0;
1856 cellDetails[i][j].h = 0.0;
1857 cellDetails[i][j].parent_i = i;
1858 cellDetails[i][j].parent_j = j;
1859
1860 /*
1861 Create an open list having information as-
1862 <f, <i, j>>
1863 where f = g + h,
1864 and i, j are the row and column index of that cell
1865 Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
1866 This open list is implenented as a set of pair of pair.*/
1867 set<pPair> openList;
1868
1869 // Put the starting cell on the open list and set its
1870 // 'f' as 0
1871 openList.insert(make_pair (0.0, make_pair (i, j)));
1872
1873 // We set this boolean value as false as initially
1874 // the destination is not reached.
1875 bool foundDest = false;
1876
1877 while (!openList.empty())
1878 {
1879 pPair p = *openList.begin();
1880
1881 // Remove this vertex from the open list
1882 openList.erase(openList.begin());
1883
1884 // Add this vertex to the open list
1885 i = p.second.first;
1886 j = p.second.second;
1887 closedList[i][j] = true;
1888
1889 /*
1890 Generating all the 8 successor of this cell
1891
1892 N.W N N.E
1893 \ | /
1894 \ | /
1895 W----Cell----E
1896 / | \
1897 / | \
1898 S.W S S.E
1899
1900 Cell-->Popped Cell (i, j)
1901 N --> North (i-1, j)
1902 S --> South (i+1, j)
1903 E --> East (i, j+1)
1904 W --> West (i, j-1)
1905 N.E--> North-East (i-1, j+1)
1906 N.W--> North-West (i-1, j-1)
1907 S.E--> South-East (i+1, j+1)
1908 S.W--> South-West (i+1, j-1)*/
1909
1910 // To store the 'g', 'h' and 'f' of the 8 successors
1911 double gNew, hNew, fNew;
1912
1913 //----------- 1st Successor (North) ------------
1914
1915 // Only process this cell if this is a valid one
1916 if (isValid(i-1, j) == true)
1917 {
1918 // If the destination cell is the same as the
1919 // current successor
1920 if (isDestination(i-1, j, dest) == true)
1921 {
1922 // Set the Parent of the destination cell
1923 cellDetails[i-1][j].parent_i = i;
1924 cellDetails[i-1][j].parent_j = j;
1925 printf ("The destination cell is found\n");
1926 tracePath (cellDetails, dest);
1927 foundDest = true;
1928 return;
1929 }
1930 // If the successor is already on the closed
1931 // list or if it is blocked, then ignore it.
1932 // Else do the following
1933 else if (closedList[i-1][j] == false &&
1934 isUnBlocked(grid, i-1, j) == true)
1935 {
1936 gNew = cellDetails[i][j].g + 1.0;
1937 hNew = calculateHValue (i-1, j, dest);
1938 fNew = gNew + hNew;
1939
1940 // If it isn’t on the open list, add it to
1941 // the open list. Make the current square
1942 // the parent of this square. Record the
1943 // f, g, and h costs of the square cell
1944 // OR
1945 // If it is on the open list already, check
1946 // to see if this path to that square is better,
1947 // using 'f' cost as the measure.
1948 if (cellDetails[i-1][j].f == FLT_MAX ||
1949 cellDetails[i-1][j].f > fNew)
1950 {
1951 openList.insert( make_pair(fNew,
1952 make_pair(i-1, j)));
1953
1954 // Update the details of this cell
1955 cellDetails[i-1][j].f = fNew;
1956 cellDetails[i-1][j].g = gNew;
1957 cellDetails[i-1][j].h = hNew;
1958 cellDetails[i-1][j].parent_i = i;
1959 cellDetails[i-1][j].parent_j = j;
1960 }
1961 }
1962 }
1963
1964 //----------- 2nd Successor (South) ------------
1965
1966 // Only process this cell if this is a valid one
1967 if (isValid(i+1, j) == true)
1968 {
1969 // If the destination cell is the same as the
1970 // current successor
1971 if (isDestination(i+1, j, dest) == true)
1972 {
1973 // Set the Parent of the destination cell
1974 cellDetails[i+1][j].parent_i = i;
1975 cellDetails[i+1][j].parent_j = j;
1976 printf("The destination cell is found\n");
1977 tracePath(cellDetails, dest);
1978 foundDest = true;
1979 return;
1980 }
1981 // If the successor is already on the closed
1982 // list or if it is blocked, then ignore it.
1983 // Else do the following
1984 else if (closedList[i+1][j] == false &&
1985 isUnBlocked(grid, i+1, j) == true)
1986 {
1987 gNew = cellDetails[i][j].g + 1.0;
1988 hNew = calculateHValue(i+1, j, dest);
1989 fNew = gNew + hNew;
1990
1991 // If it isn’t on the open list, add it to
1992 // the open list. Make the current square
1993 // the parent of this square. Record the
1994 // f, g, and h costs of the square cell
1995 // OR
1996 // If it is on the open list already, check
1997 // to see if this path to that square is better,
1998 // using 'f' cost as the measure.
1999 if (cellDetails[i+1][j].f == FLT_MAX ||
2000 cellDetails[i+1][j].f > fNew)
2001 {
2002 openList.insert( make_pair (fNew, make_pair (i+1, j)));
2003 // Update the details of this cell
2004 cellDetails[i+1][j].f = fNew;
2005 cellDetails[i+1][j].g = gNew;
2006 cellDetails[i+1][j].h = hNew;
2007 cellDetails[i+1][j].parent_i = i;
2008 cellDetails[i+1][j].parent_j = j;
2009 }
2010 }
2011 }
2012
2013 //----------- 3rd Successor (East) ------------
2014
2015 // Only process this cell if this is a valid one
2016 if (isValid (i, j+1) == true)
2017 {
2018 // If the destination cell is the same as the
2019 // current successor
2020 if (isDestination(i, j+1, dest) == true)
2021 {
2022 // Set the Parent of the destination cell
2023 cellDetails[i][j+1].parent_i = i;
2024 cellDetails[i][j+1].parent_j = j;
2025 printf("The destination cell is found\n");
2026 tracePath(cellDetails, dest);
2027 foundDest = true;
2028 return;
2029 }
2030
2031 // If the successor is already on the closed
2032 // list or if it is blocked, then ignore it.
2033 // Else do the following
2034 else if (closedList[i][j+1] == false &&
2035 isUnBlocked (grid, i, j+1) == true)
2036 {
2037 gNew = cellDetails[i][j].g + 1.0;
2038 hNew = calculateHValue (i, j+1, dest);
2039 fNew = gNew + hNew;
2040
2041 // If it isn’t on the open list, add it to
2042 // the open list. Make the current square
2043 // the parent of this square. Record the
2044 // f, g, and h costs of the square cell
2045 // OR
2046 // If it is on the open list already, check
2047 // to see if this path to that square is better,
2048 // using 'f' cost as the measure.
2049 if (cellDetails[i][j+1].f == FLT_MAX ||
2050 cellDetails[i][j+1].f > fNew)
2051 {
2052 openList.insert( make_pair(fNew,
2053 make_pair (i, j+1)));
2054
2055 // Update the details of this cell
2056 cellDetails[i][j+1].f = fNew;
2057 cellDetails[i][j+1].g = gNew;
2058 cellDetails[i][j+1].h = hNew;
2059 cellDetails[i][j+1].parent_i = i;
2060 cellDetails[i][j+1].parent_j = j;
2061 }
2062 }
2063 }
2064
2065 //----------- 4th Successor (West) ------------
2066
2067 // Only process this cell if this is a valid one
2068 if (isValid(i, j-1) == true)
2069 {
2070 // If the destination cell is the same as the
2071 // current successor
2072 if (isDestination(i, j-1, dest) == true)
2073 {
2074 // Set the Parent of the destination cell
2075 cellDetails[i][j-1].parent_i = i;
2076 cellDetails[i][j-1].parent_j = j;
2077 printf("The destination cell is found\n");
2078 tracePath(cellDetails, dest);
2079 foundDest = true;
2080 return;
2081 }
2082
2083 // If the successor is already on the closed
2084 // list or if it is blocked, then ignore it.
2085 // Else do the following
2086 else if (closedList[i][j-1] == false &&
2087 isUnBlocked(grid, i, j-1) == true)
2088 {
2089 gNew = cellDetails[i][j].g + 1.0;
2090 hNew = calculateHValue(i, j-1, dest);
2091 fNew = gNew + hNew;
2092
2093 // If it isn’t on the open list, add it to
2094 // the open list. Make the current square
2095 // the parent of this square. Record the
2096 // f, g, and h costs of the square cell
2097 // OR
2098 // If it is on the open list already, check
2099 // to see if this path to that square is better,
2100 // using 'f' cost as the measure.
2101 if (cellDetails[i][j-1].f == FLT_MAX ||
2102 cellDetails[i][j-1].f > fNew)
2103 {
2104 openList.insert( make_pair (fNew,
2105 make_pair (i, j-1)));
2106
2107 // Update the details of this cell
2108 cellDetails[i][j-1].f = fNew;
2109 cellDetails[i][j-1].g = gNew;
2110 cellDetails[i][j-1].h = hNew;
2111 cellDetails[i][j-1].parent_i = i;
2112 cellDetails[i][j-1].parent_j = j;
2113 }
2114 }
2115 }
2116
2117 //----------- 5th Successor (North-East) ------------
2118
2119 // Only process this cell if this is a valid one
2120 if (isValid(i-1, j+1) == true)
2121 {
2122 // If the destination cell is the same as the
2123 // current successor
2124 if (isDestination(i-1, j+1, dest) == true)
2125 {
2126 // Set the Parent of the destination cell
2127 cellDetails[i-1][j+1].parent_i = i;
2128 cellDetails[i-1][j+1].parent_j = j;
2129 printf ("The destination cell is found\n");
2130 tracePath (cellDetails, dest);
2131 foundDest = true;
2132 return;
2133 }
2134
2135 // If the successor is already on the closed
2136 // list or if it is blocked, then ignore it.
2137 // Else do the following
2138 else if (closedList[i-1][j+1] == false &&
2139 isUnBlocked(grid, i-1, j+1) == true)
2140 {
2141 gNew = cellDetails[i][j].g + 1.414;
2142 hNew = calculateHValue(i-1, j+1, dest);
2143 fNew = gNew + hNew;
2144
2145 // If it isn’t on the open list, add it to
2146 // the open list. Make the current square
2147 // the parent of this square. Record the
2148 // f, g, and h costs of the square cell
2149 // OR
2150 // If it is on the open list already, check
2151 // to see if this path to that square is better,
2152 // using 'f' cost as the measure.
2153 if (cellDetails[i-1][j+1].f == FLT_MAX ||
2154 cellDetails[i-1][j+1].f > fNew)
2155 {
2156 openList.insert( make_pair (fNew,
2157 make_pair(i-1, j+1)));
2158
2159 // Update the details of this cell
2160 cellDetails[i-1][j+1].f = fNew;
2161 cellDetails[i-1][j+1].g = gNew;
2162 cellDetails[i-1][j+1].h = hNew;
2163 cellDetails[i-1][j+1].parent_i = i;
2164 cellDetails[i-1][j+1].parent_j = j;
2165 }
2166 }
2167 }
2168
2169 //----------- 6th Successor (North-West) ------------
2170
2171 // Only process this cell if this is a valid one
2172 if (isValid (i-1, j-1) == true)
2173 {
2174 // If the destination cell is the same as the
2175 // current successor
2176 if (isDestination (i-1, j-1, dest) == true)
2177 {
2178 // Set the Parent of the destination cell
2179 cellDetails[i-1][j-1].parent_i = i;
2180 cellDetails[i-1][j-1].parent_j = j;
2181 printf ("The destination cell is found\n");
2182 tracePath (cellDetails, dest);
2183 foundDest = true;
2184 return;
2185 }
2186
2187 // If the successor is already on the closed
2188 // list or if it is blocked, then ignore it.
2189 // Else do the following
2190 else if (closedList[i-1][j-1] == false &&
2191 isUnBlocked(grid, i-1, j-1) == true)
2192 {
2193 gNew = cellDetails[i][j].g + 1.414;
2194 hNew = calculateHValue(i-1, j-1, dest);
2195 fNew = gNew + hNew;
2196
2197 // If it isn’t on the open list, add it to
2198 // the open list. Make the current square
2199 // the parent of this square. Record the
2200 // f, g, and h costs of the square cell
2201 // OR
2202 // If it is on the open list already, check
2203 // to see if this path to that square is better,
2204 // using 'f' cost as the measure.
2205 if (cellDetails[i-1][j-1].f == FLT_MAX ||
2206 cellDetails[i-1][j-1].f > fNew)
2207 {
2208 openList.insert( make_pair (fNew, make_pair (i-1, j-1)));
2209 // Update the details of this cell
2210 cellDetails[i-1][j-1].f = fNew;
2211 cellDetails[i-1][j-1].g = gNew;
2212 cellDetails[i-1][j-1].h = hNew;
2213 cellDetails[i-1][j-1].parent_i = i;
2214 cellDetails[i-1][j-1].parent_j = j;
2215 }
2216 }
2217 }
2218
2219 //----------- 7th Successor (South-East) ------------
2220
2221 // Only process this cell if this is a valid one
2222 if (isValid(i+1, j+1) == true)
2223 {
2224 // If the destination cell is the same as the
2225 // current successor
2226 if (isDestination(i+1, j+1, dest) == true)
2227 {
2228 // Set the Parent of the destination cell
2229 cellDetails[i+1][j+1].parent_i = i;
2230 cellDetails[i+1][j+1].parent_j = j;
2231 printf ("The destination cell is found\n");
2232 tracePath (cellDetails, dest);
2233 foundDest = true;
2234 return;
2235 }
2236
2237 // If the successor is already on the closed
2238 // list or if it is blocked, then ignore it.
2239 // Else do the following
2240 else if (closedList[i+1][j+1] == false &&
2241 isUnBlocked(grid, i+1, j+1) == true)
2242 {
2243 gNew = cellDetails[i][j].g + 1.414;
2244 hNew = calculateHValue(i+1, j+1, dest);
2245 fNew = gNew + hNew;
2246
2247 // If it isn’t on the open list, add it to
2248 // the open list. Make the current square
2249 // the parent of this square. Record the
2250 // f, g, and h costs of the square cell
2251 // OR
2252 // If it is on the open list already, check
2253 // to see if this path to that square is better,
2254 // using 'f' cost as the measure.
2255 if (cellDetails[i+1][j+1].f == FLT_MAX ||
2256 cellDetails[i+1][j+1].f > fNew)
2257 {
2258 openList.insert(make_pair(fNew,
2259 make_pair (i+1, j+1)));
2260
2261 // Update the details of this cell
2262 cellDetails[i+1][j+1].f = fNew;
2263 cellDetails[i+1][j+1].g = gNew;
2264 cellDetails[i+1][j+1].h = hNew;
2265 cellDetails[i+1][j+1].parent_i = i;
2266 cellDetails[i+1][j+1].parent_j = j;
2267 }
2268 }
2269 }
2270
2271 //----------- 8th Successor (South-West) ------------
2272
2273 // Only process this cell if this is a valid one
2274 if (isValid (i+1, j-1) == true)
2275 {
2276 // If the destination cell is the same as the
2277 // current successor
2278 if (isDestination(i+1, j-1, dest) == true)
2279 {
2280 // Set the Parent of the destination cell
2281 cellDetails[i+1][j-1].parent_i = i;
2282 cellDetails[i+1][j-1].parent_j = j;
2283 printf("The destination cell is found\n");
2284 tracePath(cellDetails, dest);
2285 foundDest = true;
2286 return;
2287 }
2288
2289 // If the successor is already on the closed
2290 // list or if it is blocked, then ignore it.
2291 // Else do the following
2292 else if (closedList[i+1][j-1] == false &&
2293 isUnBlocked(grid, i+1, j-1) == true)
2294 {
2295 gNew = cellDetails[i][j].g + 1.414;
2296 hNew = calculateHValue(i+1, j-1, dest);
2297 fNew = gNew + hNew;
2298
2299 // If it isn’t on the open list, add it to
2300 // the open list. Make the current square
2301 // the parent of this square. Record the
2302 // f, g, and h costs of the square cell
2303 // OR
2304 // If it is on the open list already, check
2305 // to see if this path to that square is better,
2306 // using 'f' cost as the measure.
2307 if (cellDetails[i+1][j-1].f == FLT_MAX ||
2308 cellDetails[i+1][j-1].f > fNew)
2309 {
2310 openList.insert(make_pair(fNew,
2311 make_pair(i+1, j-1)));
2312
2313 // Update the details of this cell
2314 cellDetails[i+1][j-1].f = fNew;
2315 cellDetails[i+1][j-1].g = gNew;
2316 cellDetails[i+1][j-1].h = hNew;
2317 cellDetails[i+1][j-1].parent_i = i;
2318 cellDetails[i+1][j-1].parent_j = j;
2319 }
2320 }
2321 }
2322 }
2323
2324 // When the destination cell is not found and the open
2325 // list is empty, then we conclude that we failed to
2326 // reach the destiantion cell. This may happen when the
2327 // there is no way to destination cell (due to blockages)
2328 if (foundDest == false)
2329 printf("Failed to find the Destination Cell\n");
2330
2331 return;
2332}
2333
2334
2335// Driver program to test above function
2336int main()
2337{
2338 /* Description of the Grid-
2339 1--> The cell is not blocked
2340 0--> The cell is blocked */
2341 int grid[ROW][COL] =
2342 {
2343 { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
2344 { 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 },
2345 { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
2346 { 0, 0, 1, 0, 1, 0, 0, 0, 0, 1 },
2347 { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 },
2348 { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 },
2349 { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 },
2350 { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },
2351 { 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 }
2352 };
2353
2354 // Source is the left-most bottom-most corner
2355 Pair src = make_pair(8, 0);
2356
2357 // Destination is the left-most top-most corner
2358 Pair dest = make_pair(0, 0);
2359
2360 aStarSearch(grid, src, dest);
2361
2362 return(0);
2363}
2364
2365Limitations
2366Although being the best pathfinding algorithm around, A* Search Algorithm doesn’t produce the shortest path always, as it relies heavily on heuristics / approximations to calculate – h
2367________________________________________________________________________________________________________________________________________________________________________________________________________________
23681) Initialize keys of all vertices as infinite and
2369 parent of every vertex as -1.
2370
23712) Create an empty priority_queue pq. Every item
2372 of pq is a pair (weight, vertex). Weight (or
2373 key) is used used as first item of pair
2374 as first item is by default used to compare
2375 two pairs.
2376
23773) Initialize all vertices as not part of MST yet.
2378 We use boolean array inMST[] for this purpose.
2379 This array is required to make sure that an already
2380 considered vertex is not included in pq again. This
2381 is where Ptim's implementation differs from Dijkstra.
2382 In Dijkstr's algorithm, we didn't need this array as
2383 distances always increase. We require this array here
2384 because key value of a processed vertex may decrease
2385 if not checked.
2386
23874) Insert source vertex into pq and make its key as 0.
2388
23895) While either pq doesn't become empty
2390 a) Extract minimum key vertex from pq.
2391 Let the extracted vertex be u.
2392
2393 b) Include u in MST using inMST[u] = true.
2394
2395 c) Loop through all adjacent of u and do
2396 following for every vertex v.
2397
2398 // If weight of edge (u,v) is smaller than
2399 // key of v and v is not already in MST
2400 If inMST[v] = false && key[v] > weight(u, v)
2401
2402 (i) Update key of v, i.e., do
2403 key[v] = weight(u, v)
2404 (ii) Insert v into the pq
2405 (iv) parent[v] = u
2406
24076) Print MST edges using parent array.
2408
2409Below is C++ implementation of above idea.
2410
2411// STL implementation of Prim's algorithm for MST
2412#include<bits/stdc++.h>
2413using namespace std;
2414# define INF 0x3f3f3f3f
2415
2416// iPair ==> Integer Pair
2417typedef pair<int, int> iPair;
2418
2419// This class represents a directed graph using
2420// adjacency list representation
2421class Graph
2422{
2423 int V; // No. of vertices
2424
2425 // In a weighted graph, we need to store vertex
2426 // and weight pair for every edge
2427 list< pair<int, int> > *adj;
2428
2429public:
2430 Graph(int V); // Constructor
2431
2432 // function to add an edge to graph
2433 void addEdge(int u, int v, int w);
2434
2435 // Print MST using Prim's algorithm
2436 void primMST();
2437};
2438
2439// Allocates memory for adjacency list
2440Graph::Graph(int V)
2441{
2442 this->V = V;
2443 adj = new list<iPair> [V];
2444}
2445
2446void Graph::addEdge(int u, int v, int w)
2447{
2448 adj[u].push_back(make_pair(v, w));
2449 adj[v].push_back(make_pair(u, w));
2450}
2451
2452// Prints shortest paths from src to all other vertices
2453void Graph::primMST()
2454{
2455 // Create a priority queue to store vertices that
2456 // are being preinMST. This is weird syntax in C++.
2457 // Refer below link for details of this syntax
2458 // http://geeksquiz.com/implement-min-heap-using-stl/
2459 priority_queue< iPair, vector <iPair> , greater<iPair> > pq;
2460
2461 int src = 0; // Taking vertex 0 as source
2462
2463 // Create a vector for keys and initialize all
2464 // keys as infinite (INF)
2465 vector<int> key(V, INF);
2466
2467 // To store parent array which in turn store MST
2468 vector<int> parent(V, -1);
2469
2470 // To keep track of vertices included in MST
2471 vector<bool> inMST(V, false);
2472
2473 // Insert source itself in priority queue and initialize
2474 // its key as 0.
2475 pq.push(make_pair(0, src));
2476 key[src] = 0;
2477
2478 /* Looping till priority queue becomes empty */
2479 while (!pq.empty())
2480 {
2481 // The first vertex in pair is the minimum key
2482 // vertex, extract it from priority queue.
2483 // vertex label is stored in second of pair (it
2484 // has to be done this way to keep the vertices
2485 // sorted key (key must be first item
2486 // in pair)
2487 int u = pq.top().second;
2488 pq.pop();
2489
2490 inMST[u] = true; // Include vertex in MST
2491
2492 // 'i' is used to get all adjacent vertices of a vertex
2493 list< pair<int, int> >::iterator i;
2494 for (i = adj[u].begin(); i != adj[u].end(); ++i)
2495 {
2496 // Get vertex label and weight of current adjacent
2497 // of u.
2498 int v = (*i).first;
2499 int weight = (*i).second;
2500
2501 // If v is not in MST and weight of (u,v) is smaller
2502 // than current key of v
2503 if (inMST[v] == false && key[v] > weight)
2504 {
2505 // Updating key of v
2506 key[v] = weight;
2507 pq.push(make_pair(key[v], v));
2508 parent[v] = u;
2509 }
2510 }
2511 }
2512
2513 // Print edges of MST using parent array
2514 for (int i = 1; i < V; ++i)
2515 printf("%d - %d\n", parent[i], i);
2516}
2517
2518// Driver program to test methods of graph class
2519int main()
2520{
2521 // create the graph given in above fugure
2522 int V = 9;
2523 Graph g(V);
2524
2525 // making above shown graph
2526 g.addEdge(0, 1, 4);
2527 g.addEdge(0, 7, 8);
2528 g.addEdge(1, 2, 8);
2529 g.addEdge(1, 7, 11);
2530 g.addEdge(2, 3, 7);
2531 g.addEdge(2, 8, 2);
2532 g.addEdge(2, 5, 4);
2533 g.addEdge(3, 4, 9);
2534 g.addEdge(3, 5, 14);
2535 g.addEdge(4, 5, 10);
2536 g.addEdge(5, 6, 2);
2537 g.addEdge(6, 7, 1);
2538 g.addEdge(6, 8, 6);
2539 g.addEdge(7, 8, 7);
2540
2541 g.primMST();
2542
2543 return 0;
2544}
2545
2546Output :
2547
25480 - 1
25491 - 2
25502 - 3
25513 - 4
25522 - 5
25535 - 6
25546 - 7
25552 - 8
2556
2557Time complexity : O(E Log V))
2558________________________________________________________________________________________________________________________________________________________________________________________________________________
2559his post, implementation of simple solution is discussed.
2560
2561 Consider city 1 as the starting and ending point. Since route is cyclic, we can consider any point as starting point.
2562 Generate all (n-1)! permutations of cities.
2563 Calculate cost of every permutation and keep track of minimum cost permutation.
2564 Return the permutation with minimum cost.
2565
2566Below c++ implementation of above idea
2567// CPP program to implement traveling salesman
2568// problem using naive approach.
2569#include <bits/stdc++.h>
2570using namespace std;
2571#define V 4
2572
2573// implementation of traveling Salesman Problem
2574int travllingSalesmanProblem(int graph[][V], int s)
2575{
2576 // store all vertex apart from source vertex
2577 vector<int> vertex;
2578 for (int i = 0; i < V; i++)
2579 if (i != s)
2580 vertex.push_back(i);
2581
2582 // store minimum weight Hamiltonian Cycle.
2583 int min_path = INT_MAX;
2584 do {
2585
2586 // store current Path weight(cost)
2587 int current_pathweight = 0;
2588
2589 // compute current path weight
2590 int k = s;
2591 for (int i = 0; i < vertex.size(); i++) {
2592 current_pathweight += graph[k][vertex[i]];
2593 k = vertex[i];
2594 }
2595 current_pathweight += graph[k][s];
2596
2597 // update minimum
2598 min_path = min(min_path, current_pathweight);
2599
2600 } while (next_permutation(vertex.begin(), vertex.end()));
2601
2602 return min_path;
2603}
2604
2605// driver program to test above function
2606int main()
2607{
2608 // matrix representation of graph
2609 int graph[][V] = { { 0, 10, 15, 20 },
2610 { 10, 0, 35, 25 },
2611 { 15, 35, 0, 30 },
2612 { 20, 25, 30, 0 } };
2613 int s = 0;
2614 cout << travllingSalesmanProblem(graph, s) << endl;
2615 return 0;
2616}
2617
2618Output:
2619
262080
2621
2622________________________________________________________________________________________________________________________________________________________________________________________________________________
2623Following is the code for the calculation of the betweenness centrality of the graph and its various nodes.
2624def betweenness_centrality(G, k=None, normalized=True, weight=None,
2625 endpoints=False, seed=None):
2626 r"""Compute the shortest-path betweenness centrality for nodes.
2627
2628 Betweenness centrality of a node $v$ is the sum of the
2629 fraction of all-pairs shortest paths that pass through $v$
2630
2631 .. math::
2632
2633 c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}
2634
2635 where $V$ is the set of nodes, $\sigma(s, t)$ is the number of
2636 shortest $(s, t)$-paths, and $\sigma(s, t|v)$ is the number of
2637 those paths passing through some node $v$ other than $s, t$.
2638 If $s = t$, $\sigma(s, t) = 1$, and if $v \in {s, t}$,
2639 $\sigma(s, t|v) = 0$ [2]_.
2640
2641 Parameters
2642 ----------
2643 G : graph
2644 A NetworkX graph.
2645
2646 k : int, optional (default=None)
2647 If k is not None use k node samples to estimate betweenness.
2648 The value of k <= n where n is the number of nodes in the graph.
2649 Higher values give better approximation.
2650
2651 normalized : bool, optional
2652 If True the betweenness values are normalized by `2/((n-1)(n-2))`
2653 for graphs, and `1/((n-1)(n-2))` for directed graphs where `n`
2654 is the number of nodes in G.
2655
2656 weight : None or string, optional (default=None)
2657 If None, all edge weights are considered equal.
2658 Otherwise holds the name of the edge attribute used as weight.
2659
2660 endpoints : bool, optional
2661 If True include the endpoints in the shortest path counts.
2662
2663 Returns
2664 -------
2665 nodes : dictionary
2666 Dictionary of nodes with betweenness centrality as the value.
2667
2668
2669 Notes
2670 -----
2671 The algorithm is from Ulrik Brandes [1]_.
2672 See [4]_ for the original first published version and [2]_ for details on
2673 algorithms for variations and related metrics.
2674
2675 For approximate betweenness calculations set k=#samples to use
2676 k nodes ("pivots") to estimate the betweenness values. For an estimate
2677 of the number of pivots needed see [3]_.
2678
2679 For weighted graphs the edge weights must be greater than zero.
2680 Zero edge weights can produce an infinite number of equal length
2681 paths between pairs of nodes.
2682 """
2683
2684 """
2685 betweenness = dict.fromkeys(G, 0.0) # b[v]=0 for v in G
2686 if k is None:
2687 nodes = G
2688 else:
2689 random.seed(seed)
2690 nodes = random.sample(G.nodes(), k)
2691 for s in nodes:
2692
2693 # single source shortest paths
2694 if weight is None: # use BFS
2695 S, P, sigma = _single_source_shortest_path_basic(G, s)
2696 else: # use Dijkstra's algorithm
2697 S, P, sigma = _single_source_dijkstra_path_basic(G, s, weight)
2698
2699 # accumulation
2700 if endpoints:
2701 betweenness = _accumulate_endpoints(betweenness, S, P, sigma, s)
2702 else:
2703 betweenness = _accumulate_basic(betweenness, S, P, sigma, s)
2704
2705 # rescaling
2706 betweenness = _rescale(betweenness, len(G), normalized=normalized,
2707 directed=G.is_directed(), k=k)
2708 return betweenness
2709
2710The above function is invoked using the networkx library and once the library is installed, you can eventually use it and the following code has to be written in python for the implementation of the betweenness centrality of a node.
2711>>> import networkx as nx
2712>>> G=nx.erdos_renyi_graph(50,0.5)
2713>>> b=nx.betweenness_centrality(G)
2714>>> print(b)
2715
2716The result of it is:
2717{0: 0.01220586070437195, 1: 0.009125402885768874, 2: 0.010481510111098788, 3: 0.014645690907182346,
27184: 0.013407129955492722, 5: 0.008165902336070403, 6: 0.008515486873573529, 7: 0.0067362883337957575,
27198: 0.009167651113672941, 9: 0.012386122359980324, 10: 0.00711685931010503, 11: 0.01146358835858978,
272012: 0.010392276809830674, 13: 0.0071149912635190965, 14: 0.011112503660641336, 15: 0.008013362669468532,
2721 16: 0.01332441710128969, 17: 0.009307485134691016, 18: 0.006974541084171777, 19: 0.006534636068324543,
272220: 0.007794762718607258, 21: 0.012297442232146375, 22: 0.011081427155225095, 23: 0.018715475770172643,
2723 24: 0.011527827410298818, 25: 0.012294312339823964, 26: 0.008103941622217354, 27: 0.011063824792934858,
2724 28: 0.00876321613116331, 29: 0.01539738650994337, 30: 0.014968892689224241, 31: 0.006942569786325711,
2725 32: 0.01389881951343378, 33: 0.005315473883526104, 34: 0.012485048548223817, 35: 0.009147849010405877,
2726 36: 0.00755662592209711, 37: 0.007387027127423285, 38: 0.015993065123210606, 39: 0.0111516804297535,
2727 40: 0.010720274864419366, 41: 0.007769933231367805, 42: 0.009986222659285306, 43: 0.005102869708942402,
2728 44: 0.007652686310399397, 45: 0.017408689421606432, 46: 0.008512679806690831, 47: 0.01027761151708757,
272948: 0.008908600658162324, 49: 0.013439198921385216}
2730
2731The above result is a dictionary depicting the value of betweenness centrality of each node.