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!