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.