Wie findet man den gemeinsamen nächsten Nachbarknoten von gegebenen k verschiedenen Knoten in einem ungerichteten gewichteten Graphen?

Question

Gegeben ein ungerichteter gewichteter Graph G (V, E). und alle drei Ecken lassen u, v und w zu. Finde einen Knoten x von G. so dass dist (u, x) + dist (v, x) + dist (w, x) minimal ist. x könnte ein beliebiger Eckpunkt in G sein (u, v und w enthalten). Gibt es einen bestimmten Algorithmus für dieses Problem?

Answer 1

Sie können es mit Stack-Algorithmus wie der Pseudo-Code unten:

void FindNeigh(node node1, node node2,int graphsize) 
{ 
    byte[graphsize] isGraphProcessed; // 0 array 

    stack nodes1, nodes2; //0 arrays 
    nodes1.push(node1); 
    nodes2.push(node2); 
    bool found = false; 

    while(!nodes1.empty && !nodes2.empty()) 
    { 
     stack tmp = null; 
     for(node: nodes1) 
      for(neigh : node.neighbors) 
       if(!isGraphProcessed[neigh.id]) 
       { 
        tmp.push(neigh.id); 
        isGraphProcessed[neigh.id] = 1; // Flags for node 1 
       } 
       else if(isGraphProcessed[neigh.id] == 2) // The flag of node 2 is set 
        return neigh; 
     nodes1 =tmp; 
     tmp = null; 
     for(node: nodes2) 
      for(neigh : node.neighbors) 
       if(!isGraphProcessed[neigh.id]) 
       { 
        tmp.push(neigh.id); 
        isGraphProcessed[neigh.id] = 2; // Flags for node 2 
       } 
       else if(isGraphProcessed[neigh.id] == 1) // The flag of node 1 is set 
        return neigh; 
     nodes2 = tmp; 
    } 
    return NULL; // don't exist 
} 

Wie es

• funktioniert starten Sie von beiden Kanten des Graphen
• Sie überprüfen Nachbarn in einem Stapel
• Wenn ein Nachbar bereits im Stapel des anderen Knotens hinzugefügt wurde, bedeutet das, dass es alrea hat dy wurde vom anderen Knoten erreicht -> Er ist der nächste Knoten. Wir geben es zurück.
• Wenn nichts gefunden wird, machen wir dasselbe mit dem Nachbarn der Neigbors (und so weiter rekursiv), bis etwas gefunden ist.
• Wenn Knoten2 nicht von node1 erreichen kehrt 0.

Hinweis: Dieser Algorithmus arbeitet, um den minimalen Abstand zwischen zwei Kanten zu finden. Wenn Sie dies für 3 Kanten tun möchten, können Sie einen dritten Stapel hinzufügen und nach dem ersten Knoten suchen, der die 3 Markierungen (z. B. 1, 2 und 4) aufweist.

Hoffe, es hilft :)

Answer 2

Wenn k groß ist und es keine negativen Flanke Kosten Zyklen dann können Floyd Warshall-Algorithmus arbeiten. Es läuft in O(|V|^3) Zeit und nach seiner Fertigstellung haben wir die gesamte kürzeste Distanz-Matrix und wir können die kürzesten Abstände zwischen zwei beliebigen Ecken in O(1) Zeit bekommen. Dann scannen Sie einfach und suchen Sie nach dem besten Knoten x, der die kleinste Summe des Gesamtentfernungswerts aus den k Scheitelpunkten ergibt.