graph - 图论中的松弛条件是什么

Question

我正在尝试理解图论的主要概念及其算法。大多数算法似乎都包含“松弛条件”，我不确定这是什么。

请有人给我解释一下。

dijkstras 算法就是一个例子，这里是伪代码。

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:           // Initializations
 3          dist[v] := infinity               // Unknown distance function from source to v
 4          previous[v] := undefined          // Previous node in optimal path from source
 5      dist[source] := 0                     // Distance from source to source
 6      Q := the set of all nodes in Graph
    // All nodes in the graph are unoptimized - thus are in Q
 7      while Q is not empty:                 // The main loop
 8          u := vertex in Q with smallest dist[]
 9          if dist[u] = infinity:
 10              break                         // all remaining vertices are inaccessible from source
 11          remove u from Q
 12          for each neighbor v of u:         // where v has not yet been removed from Q.
 13              alt := dist[u] + dist_between(u, v)
 14              if alt < dist[v]:             // Relax (u,v,a)
 15                  dist[v] := alt
 16                  previous[v] := u
 17      return dist[]

谢谢

Answer 1

放松步骤:

• 您有两个节点，u和v
• 对于每个节点，到源节点都有一个暂定距离(对于除源之外的所有节点，它从正无穷大开始，并且只会减小直至达到最小值)。<

放松步骤基本上是问这个:

• 我已经知道我可以联系 v有一段距离的路径dist[v] 。我可以通过访问 v 来改进这一点吗？通过u反而？ (后者的距离为 dist[u] + weight(u, v) )

图形化:

s ~~~~~~~> v
 \         ^
  \        |
   \~~~~~> u

你知道一些路径s~>v其中距离dist[v] ，并且您知道一些路径 s~>u其中距离dist[u] 。如果dist[u] + weight(u, v) < dist[v] ，然后路径s~>u->v短于s~>v ，所以你最好使用那个!

(我写 a~>b 表示从 a 到 b 的任意长度的路径，而 a->b 我的意思是从 a 到 b 的直接单边)。

您可能还想查看此讲座:http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed17.htm