56

relaxation of an edge在图论的背景下是什么意思？我在研究 Dijkstra 的单源最短路径算法时遇到了这个问题。

4

6 回答 6

56

这是对算法的一个很好的描述，它也解释了松弛的概念。

“松弛”的概念来自对最短路径的估计与螺旋拉伸弹簧的长度之间的类比，它不是为压缩而设计的。最初，最短路径的成本被高估了，被比作伸长的弹簧。随着找到更短的路径，估计成本降低，弹簧放松。最终，如果存在最短路径，则找到最短路径，并且弹簧已松弛到其静止长度。

于 2012-10-08T13:23:57.903 回答
33

Dijkstra 算法中的松弛过程是指更新连接到顶点 v 的所有顶点的成本，如果这些成本可以通过包含经过 v 的路径得到改善。

于 2012-10-08T13:25:36.893 回答
11

放松边（您也可以在其他最短路径算法中找到这个概念）试图通过使用另一个顶点来降低到达顶点的成本。

您正在计算从一个起始顶点（例如S）到所有其他顶点的距离。在某些时候，你有中间结果——当前的估计。放松是您检查某些顶点u和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)

其中est(S,a)是距离的当前估计值，dist(a,b)是图中相邻的两个顶点之间的距离。

您在放松过程中基本上检查的是天气您当前从a到b的估计可以通过“转移”通过c的路径来改进（这种“转移”将是从a到c和从c到b的路径长度）。

于 2012-10-08T13:31:48.923 回答
1

边缘松弛过程

初始化

在最短路径算法中，您首先将零路径成本分配给起始节点（例如S），并将无穷大的路径成本分配给每个其他节点（例如A，E）。

最短路径_01

S := new Node()
A := new Node()
E := new Node()

// To go from S to S is zero
S.path_cost = 0

// high cost
A.path_cost = 1000 // "infinity"
E.path_cost = 1000 // "infinity"

边缘松弛

无限是我们可以拥有的最高成本，因此我们希望尽可能将“放松”降低到更低的成本。为此，我们计算起始节点和另一个节点之间的路径成本（例如a或ab），如果该路径成本较小，则更新该节点的路径成本。

最短路径_02

a := 3
b := 5

SS := S.path_cost + 0
if (S.path_cost > SS) {
  // 0 !> 0 + 0
  S.path_cost = SS
}

Sa := S.path_cost + a
if (A.path_cost > Sa) {
  // 1000 > 0 + 3
  A.path_cost = Sa
  // A = 0 + 3
}

ab := A.path_cost + b
if (E.path_cost > ab) {
  // 1000 > 3 + 5
  E.path_cost = ab
  // E = 3 + 5
}

重复边缘松弛

最短路径_03

c := 1

Sc := S.path_cost + c
if (E.path_cost > Sc) {
  // 8 > 0 + 1
  E.path_cost = Sc
  // E = 0 + 1
}
于 2021-04-05T22:11:58.137 回答
0

让我们在图中假设如果我们有 (u,v)∈ E 其中 w(u,v)=10 那么如果在它们之间添加第三个顶点，例如 w(u,y)=1 和 w(y,v)= 3 现在我们在 u 和 v 之间找到一条权重为 1+3=4<10 的路径。现在我们将第二条路径视为最短路径，即 (u,y,v) 并将忽略第一条路径，这是松弛。

于 2018-05-23T15:27:00.370 回答
0

边缘松弛。

放松一条边 v -> w 意味着测试从 s 到 w 的最知名方式是否是从 s 到 v，然后从 v 到 w 取边，如果是，则更新我们的数据结构。

Java代码：

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;
    }
}

还有顶点松弛。这意味着放松从给定顶点指向的所有边。

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

来自https://algs4.cs.princeton.edu/44sp/

于 2019-05-24T15:28:23.040 回答