This code is supposed to find, in a graph, the node with the smallest maximum distance to all the other nodes. The problem from Quora is :
How do I find the node that has the least maximum distance to all the other nodes in a tree? "So you're thinking about moving into an unknown city. You have been given a map of the city and want to get a house by the street corner that has the least maximum distance to all the other street corners. (Think the street corners as nodes, and the way between them as edges.)"
For instance, in this example graph:
2 is the node that has the least maximum distance to all other nodes. I found out that the complexity is \$O(n*(n*m))\$, and that works great when I have less than 5000 nodes. What could I possibly fix to make this solution handle nodes >100 000? Should I use, for instance, iteration instead of recursion?
I have done some "minor" tweaks, replacing all cout
and cin
With printf
and scanf
, and decreased the execution time by 40ms.
#include <cstudio>
#include <queue>
#include <vector>
int biggest_dist(int n, int v, const vector< vector<int> >& graph)
{ //This function finds the diameter of thegraph
int INF = 2 * graph.size(); // Bigger than any other length
vector<int> dist(n, INF);
dist[v] = 0;
queue<int> next;
next.push(v);
int bdist = 0; //biggest distance
while (!next.empty()) {
int pos = next.front();
next.pop();
bdist = dist[pos];
for (int i = 0; i < graph[pos].size(); ++i) {
int nghbr = graph[pos][i];
if (dist[nghbr] > dist[pos] + 1) {
dist[nghbr] = dist[pos] + 1;
next.push(nghbr);
}
}
}
return bdist;
}
int main()
{
int N; scanf("%i", &N);
int minst;
vector< vector<int> > graph(N);
vector<int> noder;
for (int i = 0; i < N - 1; ++i) {
int a, b;
scanf("%d %d", &a, &b);
graph[a].push_back(b);
graph[b].push_back(a);
}
int answer = 0;
int dis = biggest_dist(N, 0,graph);
int maxdist;
for (int j = 0; j < N-1; ++j)
{
maxdist = biggest_dist(N,j, graph);
if (maxdist < dis)
{
dis = maxdist;
answer = j;
}
}
printf("%d", answer);
return 0;
}