Problem 6 - Graphs

For a complete directed graph with vertex set $V=\{v_1, v_2, \dots, v_n\}$, denote the length of edge from $v_i$ to $v_j$ by $d_{ij}$. Setting $d_{ii}=0$, its distance matrix $D$ is simply $D=(d_{ij})$. In executing matrix multiplications, replace the ordinary multiplication between elements by the addition and replace the ordinary addition between elements by the operation taking the minimum among them. An example of $n=3$ is as follows:

$$\left(\begin{tabular}{ccc} 0 & 1 & 3 \\ 4 & 0 & 1 \\ -2 & 5 & 0... ...gin{tabular}{ccc} 0 & 1 & 2 \\ -1 & 0 & 1 \\ -2 & -1 & 0\end{tabular}\right)$$

$$\left[=\left(\begin{tabular}{ccc} min\{0+0, 1+4, 3-2\} & min\{0+1... ... 0-2\} & min\{-2+1,5+0,0+5\} & min\{-2+3,5+1,0+0\} \end{tabular}\right)\right]$$

1.

Describe the meaning of $D^2$.

2.

Describe the meaning of $D^{n-1}$.

3.

Does $D^{n-1}\neq D^n$ hold for some case? If yes, describe when it holds, and otherwise prove the inequality does not hold.

4.

Devise a fast algorithm to compute $D^{n-1}$.