知识卡片
最短路线性规划最大化目标距离
在目标可达且模型所含全部边均无负权环时,令变量dᵥ满足dₛ=0及每条边的dᵥ≤dᵤ+w(u,v)。
这些不等式给目标点距离设上界;最大化dₜ才将其推到最短路权重。
若仅排除源点可达的负环,不连通负环仍会使整组约束不可行。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第29章 线性规划 · 查看原书依据
Therefore, it makes sense to maximize dv for all vertices v on a shortest path from s to t subject to these constraints, and maximizing dt achieves this goal. This linear program has |V| variables dv, one for each vertex v ∈ V. It also has |E| + 1 constraints: one for each edge, plus the additional constraint that the source
参考来源
- 位置:《算法导论(第4版)》第29章《线性规划》(OEBPS/chapter029.xhtml,文本字符[25000,30000))。
- 结论依据:第29章最短路 LP 对图中每条边设约束并固定 dₛ=0,再最大化 dₜ;环上约束求和可见任何负权环都会造成不可行。
- 原始内容:Therefore, it makes sense to maximize d v for all vertices v on a shortest path from s to t subject to these constraints, and maximizing d t achieves this goal. This linear program has | V | variables d v , one for each vertex v ∈ V . It also has | E | + 1 constraints: one for each edge, plus the additional constraint that the source