Given a distance matrix with some blanks, is there any way to fill the blanks, ensuring triangle inequality? We have a $N \times N$ distance matrix with: all $(i,i)$ cells are $0$; some cells are already filled with certain numbers while others are left blank. All $(i,j)$ cells with $i \ne j$ have to be positive. (All the items already in the matrix must satisfy triangle inequality)
Now, we want to fill the blanks with certain numbers such that the network satisfies the triangle inequality, which means $(j,i)+(i,k) \ge (j,k)$ for any $i,j,k$.
An easier version is: given the matrix is symmetric; a harder version is without the symmetric condition.
Definitely we can check each pair by using brute force method, but is there any smart way to do the job?
 A: (I'd posted an original answer but deleted it when I discovered a counterexample.)
In general, it's possible that the incomplete initial matrix doesn't admit a completion which respects the triangle inequality. Consider the following (symmetric) matrix $\{A_{i,j}\}$:
$\begin{bmatrix}0 & 1 & & 1 \\ 1 & 0 & 4 & x \\ & 4 & 0 & 1 \\ 1 & x & 1 & 0 \end{bmatrix}$
where we are looking to find $x = A_{2,4} = A_{4,2}$ such that the triangle inequality is preserved. Then we must have:
$x \leq 2$ (since $A_{1,2} + A_{1,4} \geq A_{2,4}$),
but we must also have:
$x \geq 3$ (since $A_{4,2} + A_{4,3} \geq A_{2,3}$).
But $x \leq 2$ and $x \geq 3$ is a contradiction, so there is no such $x$ which satisfies the triangle inequality.
I guess this leads to the follow-up question: How do we determine whether or not an incomplete matrix admits a completion satisfying the triangle inequality?
A: As per Z. Xu's comment let's consider a slightly different constraint on the matrix, namely that
$$\sum_i^{m-1} (j_i,j_{i+1}) \geq (j_1,j_m)$$
Whenever all the matrix entries in the above inequality are non-blank.
We can consider the matrix as representing a graph (network) with nodes labelled $1,\ldots,N$ and an edge from $j$ to $k$ labelled $(j,k)$ for each non-blank entry $(j,k)$ in the matrix. N.B. If the matrix is symmetric then the graph will be undirected, if the matrix is non-symmetric then the graph is directed.
With this in mind, the above condition is equivalent to saying that if there is an edge from node $j$ to node $k$ in the graph then it is the shortest path from $j$ to $k$.
If the original incomplete graph satisfies this property, I believe the following algorithm can be used to complete the graph (and hence the matrix).


*

*Choose a pair of nodes $j,k$  such that there is currently no edge from $j$ to $k$ (i.e. the matrix entry $(j,k)$ is blank).

*Using Dijkstra's algorithm, compute the length $l$ of the shortest path from $j$ to $k$, or set $l=\infty$ if no such path exists.

*If $l < \infty$, add an edge from $j$ to $k$ labelled $l$ (i.e. add entry $(j,k)$ to the matrix with value $l$).

*If $l=\infty$, add an edge from $j$ to $k$ labelled $M$ where $M$ is the maximum value of any edge label in the current graph (i.e. add entry $(j,k)$ to the matrix with value $M$ where $M$ is the maximum entry in the matrix).

*Repeat steps 1 to 4 until there is an edge between each pair of nodes in the graph.


I believe that should work. I haven't got a formal proof, the heart of any proof would be an inductive step where you show that adding an edge according to steps 1 to 4 preserves the inequality.
