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

Question

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

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

Answer 1

Dijkstra 算法在两个簇之间的工作方式与两个顶点之间的工作方式基本相同。从距离为 0 的源集群中的所有顶点开始，然后继续逐步构建更长的路径，直到在目标集群中找到其中一个顶点。如果有帮助，您可以这样想：将两个集群中的所有顶点与 0 成本边连接在一起，然后找到从任何特定源顶点到任何特定目标顶点的最短路径。您选择哪个并不重要，因为 0 成本边确保集群中的所有内容与其他所有内容的距离相同。