Dijkstra算法中边的松弛

Question

Dijkstra算法中边的松弛

algorithmgraph-theorygraph-algorithm

58

在图论的背景下，“边的松弛”是什么意思？我在学习狄克斯特拉（Dijkstra）算法以寻找单一源最短路径时遇到了这个问题。

- Geek

8个回答

33

Dijkstra算法中的松弛过程指的是如果通过顶点v的路径可以改进与v相连的所有顶点的代价，那么就更新这些顶点的代价。

- digitalvision

1

这并没有回答问题，问题是关于放松边缘意味着什么。 - user1142217

12

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

您正在计算从起始顶点（比如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之间的距离。

在松弛过程中，您要检查的基本上是从a到b的当前估计是否可以通过“改变路径”通过c来改进（这种“改变路径”的长度将是从a到c，再从c到b的路径长度）。

- penelope

3

边缘松弛过程

初始化

在最短路径算法中，高成本告诉算法“不要走那条路”。因此，默认情况下，我们只知道起始节点是最短路径的一部分，而所有其他节点仍未确定。因此，我们将起始节点（例如S）的成本设为零，将每个其他节点（例如A，E）的成本设为无穷大。

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

// low cost
S.edge_cost = 0

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

放松

高成本只是暂时的，现在我们需要“放松”降低成本。为此，我们使用边缘成本（例如a、b和c），并在节点较低时更新它们。

// Check if S node can be reduced
// SS := S.edge_cost + S.edge_cost // 0 + 0 = 0
// if (S.edge_cost > SS) { // 0 > 0 => false
//   S.edge_cost = SS
// }

// Check if A node can be reduced
SA := S.edge_cost + a // 0 + 3 = 3
if (A.edge_cost > SA) { // 1000 > 3 => true
  A.edge_cost = SA // 3
}

// Check if E node can be reduced
AE := A.edge_cost + b // 3 + 5 = 8
if (E.edge_cost > AE) { // 1000 > 8 => true
  E.edge_cost = AE // 8
}

放松重复

// Note: The nodes hold memory,
//  so the `edge_cost` remembers the previous cost,
//  and that's what the edge is compared against

SE := S.edge_cost + c // 0 + 1 = 1
if (E.edge_cost > SE) { // 8 > 1 => true 
  E.edge_cost = SE // 1
}

- tim-montague

这似乎是在定义松弛顶点的含义，但它并没有定义松弛边的含义。 - user1142217

@user1142217 - 边缘是SA，SE和AE。随着顶点A和E从无穷远处放松，边缘也会放松。 - tim-montague

1

我还不能发表评论，但我想试着回答接受答案的评论。

用户3245268发表评论：

为什么要说EDGE是松弛的，而不是到节点v的路径。为什么是“EDGE”松弛而不是“PATH”松弛？

通常之所以松弛边缘而不是路径，可能是因为在执行Dijkstra算法期间，没有任何路径的显式表示；此时您拥有的只是每个节点的前任指针。

显然，如果松弛边缘，则隐含的新最短路径也会被松弛，因此这并不违反松弛路径的类比。但是在算法中，当您尚未真正考虑路径时，在路径上放松一条边的概念在上下文中同样有意义。

Alexey发表评论：

这种解释几乎没有意义。弹簧是边缘吗？那么当一个弹簧松弛时，其他弹簧会发生什么情况？为什么它们不是从一开始就放松的？或者弹簧是最短路径吗？那么它们在什么范围内是不可压缩的？为什么要谈论“放松弹簧”而不是“缩短绳子”？我听说“放松”来自运筹学，但我还无法弄清楚细节...

是的，弹簧就是边缘。

当一个弹簧被放松时，子图的某些部分中的一些“张力”可能会释放，因此其他一些弹簧也可能会放松。

在开始时，从起始节点到任何其他节点的（初步）最短距离被初始化为无穷大，因此所有弹簧都被拉伸到无穷远。

弹簧应该是“不可压缩[超出其静止状态]”，但我认为这相当令人困惑，而图的另一种模型“绳索模型”则更容易理解。绳索可以

- 拉伸到其适当长度 - 在它们尚未被探索时过度拉伸 - 当它们不是任何最短路径的一部分时，只是悬挂着

在放松边缘时，“新最短路径”的边缘从过度拉伸到刚好拉伸，而“旧最短路径”的边缘从拉伸到松弛。

- bigrob

0

假设在图中，如果(u,v)∈E且w(u,v)=10，则如果在它们之间添加第三个顶点，如w(u,y)=1和w(y,v)=3，现在我们找到了一条权重为1+3=4<10的u和v之间的路径。现在我们将考虑第二条路径(u,y,v)为最短路径，并忽略第一条路径，这就是松弛操作。

- siddique

0

看一下https://www.youtube.com/watch?v=2E7MmKv0Y24&t=1336s 时间：28:30。有趣的是最短路径却处于紧张状态，这对我来说正好相反于“放松”。嗯，算了。

- user825628

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/

- GraceMeng

1

这并不是特别清晰，但至少与之前的答案不同，它试图回答有关放松边缘意味着什么的问题。 - user1142217

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- krjampani · Accepted Answer

这里有一个描述算法并解释松弛概念的好文章。

“松弛”这个概念来源于将最短路径的估计值与弹簧的长度进行类比。弹簧一般不用于压缩，因此最短路径的代价最开始是一个高估值，就像拉开的弹簧一样。随着发现更短的路径，估价会逐渐降低，弹簧会逐渐松弛。当最短路径被找到时，如果存在的话，弹簧已经松弛到其原始长度。