simplify/reduce 图的算法

Question

是否有基于边成本缩短路径（并删除节点）的算法？我无法用语言表达得太好，所以我希望这些图片能够很好地概括它：

Answer 1

您是在寻找开箱即用的东西，还是在寻找关于如何自己实现它的算法想法？后者我可以帮你。

你想要做的是调用 contraction 个顶点，这些顶点正好有 2 个邻居，即度数 2。

要实现这一点，请执行以下操作：

while exists vertex v with degree 2:
    - remove v and the 2 outgoing edges
    - add a new edge between the neighbours of v
    - the weight of the new edge is the sum of the weights of the deleted edge

也就是说，如果你有图表的以下部分： u ---2--- v ---5--- w 并应用收缩，你最终得到 u ---7--- w。

只需反复执行此操作，直到没有顶点机智度 2 剩余，即可将第一张图片中的图形转换为第二张图片中的图形。

当然，确切的实施细节将取决于您在 Python（或正在使用的任何其他语言）中用于表示图形的数据结构。