A Linear Programming Formulation for the Shortest Path Problem
给定一个有向图
(
V
,
A
)
(V, A)
(V,A)，边
(
i
,
j
)
(i, j)
(i,j) 的权重
w
i
j
w_{ij}
wij?，从
s
s
s 到
t
t
t 的最短路问题可以规划成：
min
?
x
??
∑
(
i
,
j
)
∈
A
w
i
j
x
i
j
s.t.?
for?all?
??
i
,
????
∑
j
x
i
j
?
∑
j
x
j
i
=
{
1
,
?if?
i
=
s
?
1
,
?if?
i
=
t
0
,
?otherwise?
for?all?
??
i
,
j
????
x
i
j
≥
0
\begin{aligned} \min_{\mathbf{x}} \; & \sum_{(i, j) \in A} w_{ij} x_{ij} \\ \text{s.t. } & \text{for all }\; i, \;\; \sum_{j} x_{i j}-\sum_{j} x_{j i}= \begin{cases}1, & \text { if } i=s \\ -1, & \text { if } i=t \\ 0, & \text { otherwise }\end{cases} \\ & \text{for all }\; i, j \;\; x_{ij} \geq 0 \end{aligned}
xmin?s.t.??(i,j)∈A∑?wij?xij?for?all?i,j∑?xij??j∑?xji?=??????1,?1,0,??if?i=s?if?i=t?otherwise??for?all?i,jxij?≥0?
x
i
j
x_{ij}
xij? 用以指示边
(
i
,
j
)
(i, j)
(i,j) 是否位于路径上。
|