wake-up-neo.com

Entspannung eines Randes im Dijkstra-Algorithmus

Was bedeutetrelaxation of an Edgeim Zusammenhang mit der Graphentheorie? Ich bin auf dieses Problem gestoßen, als ich den Dijkstra-Algorithmus für den kürzesten Weg aus einer Hand studierte.

31
Geek

Hier ist Eine nette Beschreibung des Algorithmus, die auch den Begriff der Entspannung erklärt.

Der Begriff "Entspannung" stammt aus einer Analogie zwischen der Schätzung des kürzesten Weges und der Länge einer Schraubenzugfeder, die ist nicht für die Komprimierung ausgelegt. Anfänglich sind die Kosten des kürzesten Weg ist ein überschätzter, verglichen mit einem gestreckten Frühling. Wie kürzer Pfade gefunden werden, werden die geschätzten Kosten gesenkt und die Feder ist entspannt. Eventuell wird der kürzeste Pfad, falls vorhanden, gefunden und Die Feder ist auf ihre ruhende Länge entspannt.

39
krjampani

Der Entspannungsprozess im Dijkstra-Algorithmus bezieht sich auf die Aktualisierung der Kosten aller mit einem Knoten v verbundenen Scheitelpunkte, wenn diese Kosten durch Einbeziehung des Pfads über v verbessert würden.

22
digitalvision

Beim Entspannen einer Kante (ein Konzept, das Sie auch in anderen Algorithmen für den kürzesten Weg finden können) wird versucht, die Kosten für das Erreichen eines Scheitelpunkts durch Verwendung eines anderen Scheitelpunkts zu senken.

Sie berechnen die Entfernungen von einem Anfangsscheitelpunkt, z. B.S, zu allen anderen Scheitelpunkten. Irgendwann haben Sie Zwischenergebnisse - aktuelle Schätzungen. Die Relaxation ist der Prozess, bei dem Sie überprüfen, für einige Knoten u und v :

if directly_connected(v, u)
    if est(S, v) > est(S, u) + dist(u,v)
       est(S, v) = est(S, u) + dist(u, v)

dabei ist est(S,a) die aktuelle Schätzung der Entfernung und dist(a,b) die Entfernung zwischen zwei Scheitelpunkten, die im Diagramm Nachbarn sind.

Grundsätzlich überprüfen Sie im Entspannungsprozess, ob Ihre aktuelle Schätzung von a nach b durch "Umleiten" des Pfads durch c verbessert werden könnte (diese "Umleitung" wäre die Länge eines Pfades von a nach c und von c nach b ).

8
penelope

nehmen wir an, in der Grafik gilt: Wenn wir (u, v) E haben, dann ist w (u, v) = 10 v) = 3 Nun finden wir einen Pfad zwischen u und v mit dem Gewicht 1 + 3 = 4 <10. Nun betrachten wir den zweiten Weg als den kürzesten, der (u, y, v) ist und den ersten Weg ignorieren wird, dies ist Entspannung.

0
siddique

Kantenentspannung.

Eine Kante entspannen v -> w bedeutet, zu testen, ob der bekannteste Weg von s nach w von s nach v ist, dann die Kante von v nach w zu nehmen und in diesem Fall unsere Datenstrukturen zu aktualisieren.

Java-Code:

private void relax(DirectedEdge e) {
    int v = e.from(), w = e.to;
    if (distTo[w] > distTo[v] + e.weight()) {
        distTo[w] = distTo[v] + e.weight();
        edgeTo[w] = e;
    }
}

Es gibt auch Scheitelpunktentspannung. Das bedeutet, alle Kanten, die von einem bestimmten Scheitelpunkt ausgehen, zu lockern.

private void relax(EdgeWeightedGraph G, int v) {
    for (DirectedEdge e : G.adj(v)) {
        relax(e);
    }
}

Von https://algs4.cs.princeton.edu/44sp/

0
GraceMeng