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 analize Paper that Christopher found but still don’t know how could I implemnt this to my problem! Trying to be more specified let’s look at grid graph: Grid graph

I want to add k shortcut edges to minimize maximum distance:
Example: Grid graph with shortcuts

So the question in what is the which nodes to connect, and how to proof that this is the best solution!