Let $w = \{w(i,j)\}_{1 \leq i,j \leq m}$ be an $m \times m$ symmetric matrix with non-negative real entries such that $w(i,j)=0$ if and only if $i=j$. Show that $$d(i,j)=\min\left\{\sum_{j=0}^{k-1}w(i_j,i_{j+1}) \mid k \geq 1, i_0=i, i_k=j,i_j \in \{1,2,...,m\}\right\}$$ is a metric on $\{1,...,m\}$.
Attempt:
The non-negativity of $d(i,j)$ is evident.
Claim 1: $d(i,j)=0$ iff $i=j$
Proof: When $i=j$, $d(i,i)= \min\left\{\sum_{j=0}^0w(i_0,i_k)=w(i,j)=0,...\right\}=0$.
Conversely, let $d(i,j)=0$. By the given condition, $w(i,j)$ is $0$ only when $i=j$ and all the other elements of the matrix are $>0$. So the only way out is $i=j$.
$\mathbf{Symmetry:} $ $$ d(i,j)=\min\left\{\sum_{j=0}^{k-1}w(i_j,i_{j+1}) \mid k \geq 1, i_0=i, i_k=j,i_j \in \{1,2,...,m\}\right\}\\ =w(i,i_1)+w(i_1,i_2)+...+w(i_{k-1},j)=w(j,i_{k-1})+...+w(i_1,i)$$
Now, $i_j$ being a dummy variable and the matrix being symmetric, we map the index $k-t \mapsto t$, which gives us:
$w(j,i_1)+w(i_1,i_2)+...+w(i_{k-1},i)=d(i,j)=d(j,i)$ [It is $=d(j,i)$ since after changing index, all the sum remains same, so the $\min$ will remain the same].
$\mathbf{\text{Triangle Inequality:}}$
$$d(i,q)+d(q,j)=w(i,i'_1)+w(i'_1,i'_2)+...+w(i'_{k'-1},q)+ w(j ,i''_1)+w(i''_1,i''_2)+...+w(i''_{k''-1},q) \geq d(i,j) $$, because on the left hand side, we go via the point $q$, but when we consider $d(i,j)$, the minimum is taken over the set $$ \mathcal{A} =\left\{\sum_{j=0}^{k-1}w(i_j,i_{j+1}) \mid k \geq 1, i_0=i, i_k=j,i_j \in \{1,2,...,m\}\right\}$$, and $d(i,q)+d(q,j) \in \mathcal{A}$.
Is this correct and rigorous enough? Kindly verify.