-
Notifications
You must be signed in to change notification settings - Fork 1
/
ShortestPathviaallnode.cpp
81 lines (62 loc) · 2.67 KB
/
ShortestPathviaallnode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Solution {
public:
// Class to carry three values at a time
class tuple
{
public:
int node; // on which current node we are standing
int mask; // mask of that node
int cost; // cost of path explore by this node
tuple(int node, int mask, int cost)
{
this -> node = node;
this -> mask = mask;
this -> cost = cost;
}
};
int shortestPathLength(vector<vector<int>>& graph) {
// total number of nodes present
int n = graph.size(); // extracting size of graph
queue<tuple> q; // queue of class tuple type
// set to take care which path we have already visited
set<pair<int, int>> vis;
int all = (1 << n) - 1; // if all nodes visited then
// we don't know which node will give us shortest path so intially for all nodes we will store in our queue
for(int i = 0; i < n; i++)
{
int maskValue = (1 << i); // 2 ^ i
tuple thisNode(i, maskValue, 1); // make a tuple for every nod
q.push(thisNode); // push tuple into our queue
vis.insert({i, maskValue}); // also update into our set
}
// Implementing BFS
while(q.empty() == false) // until queue is not empty
{
tuple curr = q.front(); // extracting front tuple
q.pop(); // pop from queuu
// if mask value becomes all, that means we have visited all of our nodes, so from here return cost - 1
if(curr.mask == all)
{
return curr.cost - 1;
}
// if not, start exploring in its adjcant
for(auto &adj: graph[curr.node])
{
int bothVisitedMask = curr.mask; // current mask
// we are moving from one node o anthor node
bothVisitedMask = bothVisitedMask | (1 << adj);
// make tuple of this path
tuple ThisNode(adj, bothVisitedMask, curr.cost + 1);
// if this path is not explored i.e
// if it is not present in our set then,
if(vis.find({adj, bothVisitedMask}) == vis.end())
{
vis.insert({adj, bothVisitedMask}); // insert into set
q.push(ThisNode); // also insert into queue
}
}
}
// return -1, but this condition will never come
return -1;
}
};