Maximum distance between two nodes in a graph.

I’d came across this problem and at first I didn’t notice the constraint "The labyrinth is designed in such a way that there is exactly one path between any two free blocks. Consequently, if we find the proper hooks to connect, it is easy to find the right path connecting them. " But now, I wonder what if this constraint is not there? I don’t know whether we can solve the problem then or not because afterall we have just a graph and we need to find the maximum distance between two nodes.

PS: I know we can always find all pair shortest paths and find out the answer but it it very costly as there are n^2 nodes.

If someone has better solution to this problem then please share. thanks!