1
\$\begingroup\$

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:

enter image description here

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;
}
\$\endgroup\$
0

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$
8
  • \$\begingroup\$ The answer should be a node, not a distance. \$\endgroup\$
    – genisage
    Jan 16, 2015 at 18:54
  • \$\begingroup\$ Also, upon closer inspection, this doesn't even give the proper maximum distance. Consider a star graph with one extra vertex attached to a point. You'll get a maximum distance of 3 when the actual best pick gives you a max distance of 2. Did you misunderstand the question? \$\endgroup\$
    – genisage
    Jan 16, 2015 at 18:59
  • \$\begingroup\$ This seems to correctly find the diameter of a tree. \$\endgroup\$
    – genisage
    Jan 16, 2015 at 19:01
  • \$\begingroup\$ @genisage Yes, but a funny thing is that these problems are pretty much the same. \$\endgroup\$
    – kraskevich
    Jan 16, 2015 at 19:23
  • \$\begingroup\$ Maybe you should mention that you need to keep track of the path that gives the diameter and pick the vertex in the middle. Unless you're just trying to give hints. In which case I can delete this. \$\endgroup\$
    – genisage
    Jan 16, 2015 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.