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

Question

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

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

• 所以例如在上面的图片中，我想知道节点 (A) 是什么类型，基于其最近的集群类型节点。
• 如你所见正常node A与节点[=34]的距离为1edge/link =]Cluster 1.
• 此外，节点 A**strong text** 与节点 Cluster 2[的距离为 2 edges/links =49=].
• 因为到集群 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

此问题的最佳算法是 breadth-first 搜索。您可以在识别类型为群集的节点后立即停止搜索。