知识卡片
动态图算法随边点变化更新答案
动态图算法面对顶点、边或权重逐步增删改;每次变化后维护图问题的答案,目标是利用先前计算而非从头求解。
例如增删边后更新最小生成树或最短路。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 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.