welcher Algorithmus kürzesten Weg von einem Knoten auf einem anderen Knoten vom Typ X

Question

Ich habe ein Diagramm, herauszufinden, die von zwei Arten von Algorithmen zusammengesetzt werden können: Cluster und Normale.

brauche ich einen Weg Wunsch Knotentyp, um herauszufinden, ist meine normalen Knoten, basierend auf seinem nächsten Knoten vom Typ Cluster:

• So zum Beispiel in Bild oben, ich mag wissen, welcher Typ ist Knoten (A) basiert auf seinem nächsten Knoten vom Typ Cluster.
• Wie Sie normalen node A hat einen Abstand von 1 Kante/link Cluster 1 zum Knoten sehen kann.
• Auch Knoten A ** ** strong text hat Abstand von 2 Kanten/Links Cluster 2 zum Knoten.
• Da der Abstand zu Cluster 1 weniger ist als Entfernung zu Cluster 2. Knoten (a) ist Typ 1.
• , wenn der Abstand 2 Cluster war kürzer als der Abstand 1 Cluster dann wäre es Typ 2.

Ich verwende Javascript + d3 für diesen Graph.

Ich suchte im Internet und fand heraus, dass Djikastras Algorithmus das ist, was ich brauche, aber Djikastras braucht einen Anfangsknoten und einen Zielknoten.

Mein Problem ist:

, dass alle mein Cluster-Typ Knoten meiner Ziele sind, und ich brauche für jeden normalen Typen Knoten zu finden, die es gibt auf seinem nächsten Cluster basieren würde.

Ist Djikstra der beste Algorithmus dafür? Ich bin mir nicht sicher, ob der Algorithmus in einem ziemlich komplexen Graphen mit Hunderten von Knoten effizient funktioniert.

Dies ist mehr oder weniger, wie mein Knoten und Verbindungen aussehen:

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

Der beste Algorithmus für dieses Problem eine Breitensuche wäre. Sie können die Suche stoppen, sobald Sie einen Knoten vom Typ Cluster identifizieren.