3
$\begingroup$

enter image description here

I have this undirected graph. Red cycle and black square are all nodes. Distance between two nodes are all 1.

How do I add a new edge between two red nodes, such that starting from any red or black node and going to any other black or red node, the total distance is shortest?

For instance you can add an edge between A and N, but you cannot add G to K, or I to Q.

For instance, if I go from B to J, if I add an edge directly from B to J, the distance will decrease from 5 to 1, but the new edge doesn't cut down the distance if I go from F to J.

Giving me the name of the algorithm is appriciated. I know how to find the shortest path from one node to another, using Prim algorithm or Dijkstra's algorithm.

$\endgroup$
7
  • 3
    $\begingroup$ I other words, you want the diameter of the extended graph to be as small as possible? Or the sum of all $\binom n2$ point-to-point distances? $\endgroup$ – hmakholm left over Monica Jun 24 '17 at 8:24
  • 2
    $\begingroup$ Also, do you need to find a solution for the particular graph you show? Or an efficient algorithm that works for all undirected graphs? Or just for undirected graphs that happen to be (as this one is) trees? $\endgroup$ – hmakholm left over Monica Jun 24 '17 at 8:29
  • 2
    $\begingroup$ In your example (?), the red nodes are all leaves except for $F$. Is it an error in the figure that $F$ is red, or can there generally be internal nodes that are red? Can there be black leaves? $\endgroup$ – hmakholm left over Monica Jun 24 '17 at 8:31
  • $\begingroup$ @HenningMakholm My bad. I want the sum of all (n2)(n2) point-to-point distances. The graph is not necessarily a tree. Both black and red nodes could be leaves. $\endgroup$ – Gqqnbig Jun 24 '17 at 17:25
  • 1
    $\begingroup$ I have no better idea than brute force here. $\endgroup$ – hmakholm left over Monica Jun 24 '17 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.