如何找到多个集群之间的最短路径

Question

Dijkstra 定理谈论寻找两个顶点之间的最短路径。但是如果我们有一个 matrix/graph 有集群怎么办......现在我们需要找到这些集群之间的最短路径！这些集群之间的距离与具有不同权重的节点之间的距离相同。

正如 Matt 所建议的那样，我们可以假设集群节点之间的距离为零。这很有意义。但是，如果我们想找到一条最短路径以便所有集群都相互连接怎么办......

Answer 1

Dijkstra 算法在两个簇之间的工作方式与在两个顶点之间的工作方式基本相同。从距离为 0 的源簇中的所有顶点开始，并继续构建逐渐变长的路径，直到找到目标簇中的一个顶点。

如果有帮助，您可以这样想：将两个簇中的所有顶点与零成本边连接在一起，然后找到从任何特定源顶点到任何特定目标顶点的最短路径。选择哪个并不重要，因为 0 成本边缘确保集群中的所有内容与其他所有内容的距离相同。