Given a positive integer N up to 50, find if the following algorithm computes the longest shortest path in any connected undirected graph with N vertices. If it doesn’t, output any graph in which this algorithm doesn’t work correctly.
Algorithm (start_vertex): find out the set of vertices S having maximum value of shortest distance from start_vertex. ans = 0; for each vertex v in S temp = 0; for each vertex u in graph G: temp = max(temp, shortest distance between u and v). ans = max(ans, temp); return ans;
This problem is unusual. Instead of finding an algorithm to solve a problem, we need to find out why the given algorithm is incorrect. So, pen and paper are best to tackle this challenge!
Without loss of generality, I will assume for simplicity that there is only one vertex S furthest away from start_vertex. For the algorithm to be flawed, S can not be one the two end-points of the longest shortest path. Also, S must be closer to all vertices than the length of the longest shortest path.
The simplest way to do this is to use a longest shortest path of length 4, put S at distance 3 away from start_vertex and all other vertices at distances 1 or 2 from start_vertex.
Suppose the longest shortest path is a path like 1 - 2 - 3 - 4 - 5 (length 4). To have start_vertex at distance up to 2 to all of them, adding edges (start_vertex, 2), and (start_vertex, 4) is sufficient.
Now, we want to have S at distance 3 from start_vertex and distance at most 3 from the others so that we can’t find a path of length 4 from S. So we connect S to vertex 3.
Finally, we can connect all the other vertices to either vertices 2 or 4. This way, all of them are at distance 2 from start_vertex and distance 3 from S. Hence, the algorithm will only find paths of length up to 3.
To be able to use this construction, we need at least 7 vertices. So, there is always a counter-example if N \ge 7. We can check by brute force that it’s impossible to do this if N \leq 6.
For each input, we only need N edges, so the time complexity of this approach is O(N) per test case.