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?Wie findet man den gemeinsamen nächsten Nachbarknoten von gegebenen k verschiedenen Knoten in einem ungerichteten gewichteten Graphen?
Antwort
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 :)
Könnten Sie bitte ein wenig ausarbeiten. Ich möchte den Ablauf wissen. – Govind
Bearbeitet, um kurz zu erklären, wie das funktioniert –
Die Grafik in der Diskussion ist eine gewichtete Grafik. Die Lösung wird nicht in allen Fällen funktionieren. Denken Sie daran, ich brauche einen Knoten mit einem Minimum von dist (u, x) + dist (v, x) + dist (w, x). – Govind
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.
Hier ist die Frage nicht die kürzeste Entfernung zu finden. – Govind
@ user2242017 Um dist (u, x) + dist (v, x) + dist (w, x) zu berechnen, müssen Sie dist (u, x) kennen, was der kürzeste Abstand zwischen u und x ist. –
- 1. Kürzester Pfad in einem gewichteten Graphen mit farbigen Kanten
- 2. Wie kürzesten Weg in einem gleich gewichteten Graphen
- 3. Wie findet man den kleinsten gemeinsamen Vorfahren eines Nary-Baumes?
- 4. Finden aller nicht überlappenden Zyklen in einem ungerichteten Graphen
- 5. Finden von k nächsten Nummern zu einer gegebenen Nummer
- 6. Wie findet man ein Rect, das einem gegebenen Rect am nächsten ist, aus einer Liste?
- 7. Hinzufügen von Scheitelpunktattributen zu einem gewichteten Graphen in Python
- 8. Konvertieren gewichteten direkten zyklischen Graphen zu äquivalenten azyklischen Graphen
- 9. alle Beziehungen finden mit einem gegebenen Knoten
- 10. Scheitelpunktdarstellung eines gewichteten unidirektionalen Graphen
- 11. Schnellster Weg, um über alle gegebenen Knoten zu gehen
- 12. Finden Sie einen einfachen Pfad in einem gewichteten ungerichteten Graphen mit maximalen Kosten in Polynomialzeit? Ist es NP?
- 13. Anzahl der verbundenen Komponenten eines k-nächsten Nachbarn Graphen suchen?
- 14. Einfacher kürzester Pfad eines azyklischen ungerichteten getrennten Graphen
- 15. Algorithmen zum Identifizieren aller Zyklusbasen in einem ungerichteten Graphen
- 16. Wie findet man den längsten Pfad in einem zyklischen Graph zwischen zwei Knoten?
- 17. Fast Connected Component Identifikation in ungerichteten Graphen in R
- 18. Allgemeiner Algorithmus zum Triangulieren eines ungerichteten Graphen?
- 19. Wie berechnet man das Gesamtgewicht der Pfade von gerichteten gewichteten Graphen in DFS in einer Iteration?
- 20. Wie findet man Knoten-ID in NS2?
- 21. Wie findet man den nächsten Textbereich mit jQuery?
- 22. Machen Sie ungerichteten Graphen aus der Adjazenzliste
- 23. minimaler Schnitt zwischen zwei beliebigen Scheitelpunkten, die als Eingabe für einen ungerichteten ungewichteten Graphen verwendet werden
- 24. BST: Wie findet man den Nachfolgerschlüssel bei einem Schlüssel?
- 25. Geben Sie die minimale und maximale Anzahl von Kanten in einem ungerichteten verbundenen Graphen von n Knoten an.
- 26. Findet k am ähnlichsten Dokumente
- 27. Einbetten von Graphen in den euklidischen Raum
- 28. Wie kann ich einen gewichteten, gerichteten Graphen in Java darstellen?
- 29. Findet Hamilton-Zyklen in kubischen planaren Graphen
- 30. Finden eines Zyklus in einem ungerichteten Graph vs Finden eines in einem gerichteten Graph
Es wird schwierig sein, besser zu machen als O (log | V |), denn der schnellste bekannte Algorithmus zum Finden des kürzesten Weges zwischen zwei Punkten (Dijkstra-Algorithmus mit einem Fibonacci-Haufen) benötigt O (| E | + | V | log | V |) Zeit, und wenn Sie einen o (log | V |) Algorithmus zur Lösung Ihres Problems hätten, könnten Sie das kürzeste Pfadproblem zwischen den Punkten u und v in besserer Zeit lösen, indem Sie Ihren Algorithmus | V | -2 mal aufrufen , wobei w der Reihe nach jeder der anderen Scheitelpunkte ist und einen Weg von den Scheitelpunkten w bildet, für die der Rückgabewert x auch w war. –
Nur aus Neugier: Warum möchten Sie diesen Eckpunkt finden? Für welches Szenario ist es interessant? – ead
Ich machte eine Netzwerkeinrichtung. Der Vertex x wäre der Ort, an den ich meine Server stelle. und du, v und w wären meine Arbeitsplätze. – Govind