To solve the problem with binary search, we consider the following decision problem: “can we make the shortest distance from vertex \(1\) to vertex \(N\) greater than or equal to \(d\)?” If we can find the minimum number of edges to modify required to make the shortest distance greater than or equal to \(d\), we can compare the count with \(K\) to answer the decision problem.

If \(d = 1\)

We first consider a simple \(d=1\) case. Then the number of edges to modify coincides with the weight of the minimum cut between vertices \(1\) and \(N\), because the shortest distance is \(1\) or greater if and only if vertex \(N\) is unreachable only via edges of weight \(0\), and thus the sought count is the minimum number of edges required to be removed in order to make it impossible to reach from vertex \(1\) to reach \(N\).

The minimum cut of a graph with \(N\) vertices and \(M\) edges can be found in \(O(N^2 M)\) time by Dinic’s algorithm.

To prepare for the next section, we will rephrase this in a bit more abstract manner. Consider \(N\) variables \(x_i \; (i=1,\dots,N)\) that take \(0\) or \(1\). \(x_i\) represents the shortest distance from vertex \(1\) to vertex \(i\). For each edge \((u,v)\), suppose that a cost of \(1\) is incurred if and only if \(x_u=0\) and \(x_v=1\). The problem can be rephrased as follows: “what is the minimum total cost when \(x_1=0\) and \(x_N=1\)?” This problem is a so-called Project Selection Problem, which can be solved as a minimum cut problem.

For general \(d\)

Now we consider general \(d\). Just as for \(d=1\), consider \(N\) variables \(x_i \; (i=1,\dots,N)\) that takes values \(0,1,\dots,d\). \(x_i\) represents the shortest distance from vertex \(1\) to vertex \(i\). For each edge \((u,v)\), define the cost as follows:

• if \(x_u+1=x_v\): cost \(1\)
• if \(x_u+1<x_v\): cost \(\infty\) (because, if the shortest distance to \(u\) is \(x_u\), then the shortest distance to \(v\) never becomes greater than \(x_u+1\))

The problem is rephrased as follows: “what is the minimum total cost of the assignments of values to \(x_1,\dots,x_N\) subject to \(x_1=0\) and \(x_N=d\)?” To boil down this problem into a minimum cut problem, we deform the problem so that the variables take values \(0\) or \(1\).

Consider \(Nd\) variables \(y_{i,j} \; (i=1,\dots,N,j=1,\dots,d)\) that take values \(0\) or \(1\). Correspond \(x_i\) to \(y_{i,1}, \dots, y_{i,d}\) as follows:

• \(x_i = j \Leftrightarrow y_{i,1}=\dots=y_{i,j}=1,y_{i,j+1}=\dots,y_{i,d}=0\).

If \(y_{i,j}\) is \(0\), then \(y_{i,j+1},\dots,y_{i,d}\) also need to be \(0\); so let us incur the following cost for each \(i=1,\dots,N, \,j=1,\dots,d-1\):

• if \(y_{i,j}=0\) and \(y_{i,j+1}=1\): cost \(\infty\)

The costs with respect to \(x\) is translated to \(y\) as follows:

• if \(y_{u,j}=0\) and \(y_{v,j}=1\) \((j=1,\dots,d)\): cost \(1\)
• if \(y_{u,j}=0\) and \(y_{v,j+1}=1\) \((j=1,\dots,d-1)\): cost \(\infty\)

Under these costs incurred, one the minimize the total cost of assignments of values to the variables subject to \(y_{1,1}=0\) and \(y_{N-1,d}=1\). This can be solved as a minimum cut problem on a graph with \(Nd\) vertices and \(N(d-1)+M(2d-1)\) edges. Since \(d\) is at most \((N-1)\), the overall time complexity is \(O(N^6 (N+M) \log N)\) including the binary search. Since the constant factor is in fact very small, it is fast enough.