Какой алгоритм найти кратчайший путь узла к другому узлу X-типа

Question

У меня есть график, который может состоять из двух типов алгоритмов: Кластер и Обычный.

Мне нужен способ, чтобы выяснить тип пожеланий узла мой нормальный узел на основе его ближайшего узла типа кластера:

• Так, например, в картинке выше, я хочу знать какой тип Node (A) основывается на ближайшем узле кластера типов.
• Как вы можете видеть нормальный node A имеет расстояние 1 края/ссылки на узел Cluster 1.
• Кроме того, узел А ** ** strong text имеет расстояние 2 кромок/ссылки на узел Cluster 2.
• Поскольку расстояние до кластера 1 меньше, чем расстояние до кластера 2. Узел (a) - тип 1.
• , если расстояние до кластера 2 был короче, чем расстояние до группы 1, то было бы тип 2.

Я использую JavaScript + d3 для этого графа.

Я искал в Интернете и обнаружил, что алгоритм Джикастры может быть тем, что мне нужно, но для Джикастры нужен начальный узел и узел цели.

Моя проблема:

Это все мои узлов типа кассетных мои целей, и мне нужно найти для каждого нормального узла типа, какой типа это будет основываться на его ближайший кластере.

Является ли 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

Лучший алгоритм для этой проблемы был бы поиск в ширину. Вы можете остановить поиск, как только вы определите узел, который относится к кластеру типа.