寻找一个节点到另一个X型节点的最短路径的算法

Question

我有一个图形，可以由两种算法组成：、集群、和Normal。

我需要一种方法来找出希望节点类型是我的普通节点，基于它最近的节点类型集群：

​

​

• 例如，在上面的pic中，我想知道Node (A)是什么类型，是基于它最近的类型集群节点。
• 如您所见，普通node A与节点Cluster 1.的距离为1边缘/链接。
• 此外，节点A**strong text**与节点strong text**的距离为2边缘/链接。
• 由于到集群1的距离比到集群2的距离小，所以节点(a)是类型1。
• 如果到群集2的距离比到群集1的距离短，那么它将是类型2。

对于这个图，我使用javascript + d3。

我在互联网上搜索，发现贾贾斯塔塔的算法可能是我所需要的，但贾贾斯塔拉斯需要一个初始节点和一个目标节点。

我的问题是：

我的所有集群类型节点都是我的目标，我需要为每个普通类型的节点找到它的类型，它将基于它最近的集群。

贾克斯特拉是这方面最好的算法吗？我不确定在一个包含数百个节点的相当复杂的图中，该算法是否能有效地执行。

这或多或少是我的节点和链接的样子：

Node A = {
   name: A,
   type: normal,
   id: node_1
}

Node Cluster 1 = {
   name: Cluster 1,
   type: cluster,
   id: node_2
}

Edge or link = {
   from= node_1,
   to= node_2
}

Answer 1

解决这个问题的最佳算法是宽度优先搜索。一旦识别出一个类型为群集的节点，就可以停止搜索。