algorithm - How to reconnect an edge between nodes and get the maximum possible size?

Question

There is a graph. You can look at first picture. The graph is not directed and let's say that distance between nodes is always 1 here. However, distance can be different. So, the path of maximum length here is between the most left and the most right nodes and equals to 3 = 1 + 1 + 1

I am allowed to move only one edge between nodes in such way that I can get longer maximum path in the graph. Look at second picture:

So, the length has became 5 = 1 + 1 + 1 + 1 + 1

The goal is to move an edge and get the longest maximum path in the graph.

Please, pay attention on circled up lines between nodes. They're not edges! I just wanted to show how to traverse the graph for getting the maximum length!

I should say that input data is

{length_1, from_node_1, to_node_1}
{length_2, from_node_2, to_node_2}
{length_3, from_node_3, to_node_3}
...
{length_N, from_node_N, to_node_N}

What an algorithm should I use? I cannot do that with brute force because after moving one edge I should look for maximum path again and start from each node but the amount of nodes is about 2000...

question from:https://stackoverflow.com/questions/65940884/how-to-reconnect-an-edge-between-nodes-and-get-the-maximum-possible-size

Answer 1

It seems I've found a good method to solve this problem without brute force. As I mentioned above in commentaries, I tried this:

1. Try to remove an edge from a set of given edges;
2. Try to build two subgraphs. There is a rupture between two subgraphs because of removed edge.
3. Try to find diameters d1, d2 of two subgraphs G1, G2
4. Get the length Li = d1 + d2 + length_of_removed_edge
5. Go to point 1 and repeat this for another edge. Get Li+1
6. After running this loop, choose maximum among Li -- this is solution