← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3680

动态图算法随边点变化更新答案

理解等级:中级

动态图算法面对顶点、边或权重逐步增删改;每次变化后维护图问题的答案,目标是利用先前计算而非从头求解。

例如增删边后更新最小生成树或最短路。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第27章 在线算法 · 查看原书依据

      Dynamic graph algorithms are online algorithms on graphs, where at each step a vertex or edge undergoes modification. Typically a vertex or edge is either inserted or deleted, or some associated property, such as edge weight, changes.

    参考来源

    - 位置:《算法导论(第4版)》第27章《在线算法》(OEBPS/chapter027.xhtml,文本字符[60000,62615))。 - 结论依据:第27章章末注释定义动态图算法,列出点边增删及权重变化;要求图变动后更新问题答案且尽量复用已有计算,并以最小生成树、最短路等为例。此处不涉及缓存概率界或 Art_P880–P888。 - 原始内容:Dynamic graph algorithms are online algorithms on graphs, where at each step a vertex or edge undergoes modification. Typically a vertex or edge is either inserted or deleted, or some associated property, such as edge weight, changes.