Wie soll ich den Namen der "Relax" -Operation verstehen, wenn ich den kürzesten Weg eines Graphen berechnen soll?

Question

Meine Frage ist genau wie der Titel. Bei der Berechnung des kürzesten Pfads eines Graphen wird häufig eine Operation relax verwendet. Es ist leicht zu verstehen, warum diese Operation verwendet wird, aber die Bedeutung des Namens ist ein Rätsel für mich. Was bedeutet "relax"? Hier

ist die Probe des Dijkstra Schreiben von Pseudo-Code:

DIJKSTRA(G,w,s) 
　　1　INITIALIZE-SINGLE-SOURCE(G，s) 
　　2　S ← Φ 
　　3　Q ← V[G] 
　　4　while Q≠Φ 
　　5　 do u EXTRACT-MIN(Q) 
　　6　 S ← S∪{u} 
　　7　 for each vertex v∈Adj[u] 
　　8　  do RELAX(u，v，w) 

Und die entspannen hier:

RELAX(u,v,w) 
    1 if d[v] > d[u] + w 
      d[v] ← d[u] + w 

Answer 1

Ein Weg, über Dijkstra-Algorithmus zu denken ist, dass es die Lösung ein lineares Programm, das dem Problem des kürzesten Weges entspricht.

maximize sum for v in V of d[v] 
subject to 
d[s] = 0 
for each arc u->v, d[v] ≤ d[u] + w[u->v] (*) 

eine Zuordnung von LP Variablen vorliegt, können wir die slack jeder Eingrenzungs definieren. Die Bedeutung von Slack ist, dass, wenn es Null ist, die linke Seite der Beschränkung gleich der rechten ist, und wenn sie negativ ist, wird die Beschränkung verletzt. Hier ist der Durchhang für (*)d[u] + w[u->v] - d[v].

Sobald wir den Durchhang definiert haben, ist RELAX der Vorgang, der die Spannung (d. H. Den negativen Durchhang) unter (*) verringert.