知识卡片

普通读书笔记卡 · 3658.b.6

最短路线性规划最大化目标距离

理解等级:中级

在目标可达且模型所含全部边均无负权环时,令变量dᵥ满足dₛ=0及每条边的dᵥ≤dᵤ+w(u,v)。

这些不等式给目标点距离设上界;最大化dₜ才将其推到最短路权重。

若仅排除源点可达的负环,不连通负环仍会使整组约束不可行。

这张卡片看不懂?

已有反馈 · 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