Finding the node with the smallest maximum distance to all the other nodes

Question

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;
}

Answer 1

It's not about constant optimizations. It's all about a more efficient algorithm. Here is a simple observation: the given graph is always a tree(because it has exactly n - 1 edges)(if it is not a tree, it is not connected and it is not clear what the answer is(maybe +infinity), so I will assume that it is a tree). That's why we can use the following algorithm:

1. Pick an arbitrary vertex v.

2. Find the furthest vertex from v(let's call it u).

3. Find the furthest vertex from u(let's call it t).

4. The distance between u and t is the answer.

This solution requires only two breadth-first searches so it has a linear time complexity. Why is it correct? I will not post a formal proof here, but drawing several trees on paper should help you to understand it. It is important that a given graph is a tree(this algorithm does not work for arbitrary graphs).

This algorithm actually finds a diameter of a tree, but it is easy to solve the original problem when a diameter is found. We can just pick the center of the diameter. To do it, we can find the path from u to t(it requires a small modification in bfs: we also need to keep track of a parent for each vertex) and store in a list. After that we just need to get the middle element of the list. If the number of elements in the list is even, we can pick any of two middle elements.