# Systems of difference constraints (CLRS 22.4)

###### `111交大_33`

## 思路

首先對於任意點 $V_x \notin \{V_i, V_j\}$，對 $V_x$ 到 $V_j$ 的最短距離 $dis(V_x, V_j)$，可以考慮兩種case：
- 若 $dis(V_x, V_j)$ 由 $dis(V_x, V_i)$ 收斂，則 $dis(V_x, V_j) = dis(V_x, V_i) + w(V_i, V_j)$ ，其中 $w(V_i, V_j)$ 為 $V_i$ 和 $V_j$ 相連邊的權重。
- 若 $dis(V_x, V_j)$ 不由 $dis(V_x, V_i)$ 收斂，則必存在另一點可以收斂 $dis(V_x, V_j)$ ，此時 $dis(V_x, V_j) < dis(V_x, V_i) + w(V_i, V_j)$

綜合以上兩點，可以得出 $dis(V_x, V_j) \leq dis(V_x, V_i) + w(V_i, V_j)$ ，即 $dis(V_x, V_j) - dis(V_x, V_i) \leq w(V_i, V_j)$ 。

而 `Systems of difference constraints` 的限制式可以寫成： $x_j - x_i = w_{ij}$，令 $x_i = dis(V_x, V_i)$，並將 $w_{ij}$ 視為從 $Vi$ 到 $Vj$ 中的邊的權重(即$w_{ij} = w(i,j)$)，在圖中將兩點相連，則**求解 $dis(V_x, V_i)$ 等同求解 $x_i$**。為了符合上述 $V_x \notin \{V_i, V_j\}$ 的前提，我們可以在圖中新增一點 $V_0$ 指向所有點，權重隨意，但一般為 $0$。

<style>
strong {
background-color: yellow; /* 設置背景顏色為黃色 */
padding: 3px; /* 添加一些內邊距以增加可讀性 */
}
</style>