二维最短路NP-complete

尝试用二划分问题归约到二维最短路问题。

假设有一个集合$S$, 定义其中的元素为$a_{i}$

权函数为$w: S \rightarrow R$

定义顶点集合为$N = {(x,0), (0,x) | \forall x \in S}$

边集$E = {((a_{i},0), (a_{i+1},0)),((0,a_{i}), (a_{i+1},0)),((0,a_{i}), (0,a_{i+1})),((a_{i},0), (0,a_{i+1}))| 1 \leq i < |S|}$

定义$\large V = (\frac{\sum w(a_{i})}{2}, \frac{\sum w(a_{i})}{2})$

$$\sum$$