Assigning edge weights under shortest path constraints We are given a graph $G = (V,E)$ and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set $R\subseteq V$ and mapping $c_{a,b}: R\times R \rightarrow \mathbb{R^+}$ where $\mathbb{R}^+$ is all positive ($&gt; 0$) reals ($c_{a,b} = c_{b,a}$ for all $a,b$ and $c_{a,a} = 0$ for all $a$ ). Our edge weight assignment is constrained by the requirement that for all vertex pairs $(a,b)\in R\times R$, all paths from $a$ to $b$ need to have at least weight $c_{a,b}$  where the weight of the path is the sum of all edge weights on that path.

Now assume that there exists an assignment that satisfies all of the constraints and such that for all vertex pairs $(a,b)\in R \times R $ there exists at least one path from $a$ to $b$ whose weight is exactly equal to $c_{a,b}$.

Now consider the assignment of edge weights (*) that satisfies the constraints and minimizes the total sum of edge weights. Is it true that for all vertex pairs $(a,b)\in R \times R$ there will exist at least one path from $a$ to $b$ whose weight is exactly equal to $c_{a,b}$ ?
Yes.

Consider an exact assignment as described in your second paragraph.

If any edge has a weight $w_{a,b} &gt; c_{a,b}$ there must be an indirect path with total path weight $c_{a,b}$, This means the direct edge $ab$ will not be part of any minimal path.  We can lower the weight to $w_{a,b} = c_{a,b}$ without changing this.

Therefore, if an exact assignment exists, $w_{a,b} = c_{a,b}$ (for all a,b) will be an exact assignment.

It is clear that this is the unique assignment with minimal total weight.