My problem is to find places to put k number of shortcut edges with weight 0 to minimize maximum distance in grid graph where all edges are weighted 1! I found a related topic to my question Minimizing distance on a graph by adding shortcuts but similar to Christopher I don't understand many mathematical concepts.
I've tried to analyze Paper that Christopher found but still don't know how could I implement this to my problem! Trying to be more specified let's look at grid graph:
I want to add k shortcut edges to minimize maximum distance. Example:
So the question in what is the which nodes to connect, and how to prove that this is the best solution!