graph - 如何通过添加具有最小总权重的边来找到从源到目的地的路径

Question

我在 3-D 空间中有大约 100 个原子。每个原子是一个节点。当两个节点接近于 0.32 nm 且权重等于距离时，在两个节点之间添加边。我想找到从源节点到目标节点的路径。由于 100 个原子没有完全连接，有时我找不到路径。

我想要做的是添加一个或多个边缘以使源和目标连接。同时，我还想最小化新添加边的总权重。同样，权重是根据两个节点的距离计算的。

这是一种最小切割的反向问题。有什么算法可以帮助做到这一点吗？

非常感谢！

Answer 1

似乎一种方法是使用图搜索算法来查找最短路径，例如 Dijkstra 的算法，并且可能从两端（源和目标）工作。

唯一的区别是您无法知道是否确实存在任何边，因此您正在创建图形。所以如果你从A开始，图的节点是A、B、C、D、E。那么你需要检查AB、AC、AD和AE是否存在。如果只存在 AB，则检查 BC、BD 和 BE。

这将是 O(|V|^2)，但实际上取决于探索了多少边。

如果您只对添加长度超过 0.32 nm 的边缘感兴趣，则同样的想法也适用。只是路径长度计算发生了变化。任何小于 0.32 nm 的边缘都是零长度，或者只是短得多（因为它们变得不那么重要了）。如果最后一点不起作用，那么它会变得有点棘手。