javascript - 哪种算法可以找出一个节点到另一个X类型节点的最短路径

Question

我有一个图可以由两种算法组成:Cluster 和 Normal。

我需要一种方法来根据最近的集群类型节点找出希望的节点类型是我的正常节点:

• 所以例如在上面的图片中，我想知道节点 (A) 是什么类型，基于其最近的簇类型节点。
• 如您所见，正常节点 A 到节点 Cluster 1距离为 1 边/链接。
• 此外，节点 A**strong text** 与节点 Cluster 2距离为 2 边/链接强>.
• 因为到集群 1 的距离小于到集群 2 的距离。节点 (a) 是类型 1。
• 如果到集群 2 的距离比到集群 1 的距离短，那么它将是类型 2。

我正在为这张图使用 javascript + d3。

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

我的问题是:

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

Djikstra 的算法是最好的吗？我不确定在具有数百个节点的相当复杂的图形中该算法是否会有效执行。

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

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

解决此问题的最佳算法是广度优先搜索。一旦识别出属于集群类型的节点，您就可以停止搜索。