Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the relaxation condition in graph theory

I'm trying to understand the main concepts of graph theory and the algorithms within it. Most algorithms seem to contain a "Relaxation Condition" I'm unsure about what this is.

Could some one explain it to me please.

An example of this is dijkstras algorithm, here is the pseudo-code.

 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[]

Thanks

like image 252
alchemey89 Avatar asked Apr 07 '10 13:04

alchemey89


People also ask

What is relaxation in graph theory?

The single - source shortest paths are based on a technique known as relaxation, a method that repeatedly decreases an upper bound on the actual shortest path weight of each vertex until the upper bound equivalent the shortest - path weight.

What is relaxation of edges?

Relaxing an edge, (a concept you can find in other shortest-path algorithms as well) is trying to lower the cost of getting to a vertex by using another vertex. where est(S,a) is the current estimate of the distance, and dist(a,b) is the distance between two vertices that are neighbors in the graph.

What is node relaxation?

Relaxation step: You have two nodes, u and v. For every node, you have a tentative distance from the source node (for all nodes except for the source, it starts at positive infinity and it only decreases up to reaching its minimum).

Why is it called edge relaxation?

In general mathematically, relaxation is making a change that reduces constraints. When the Dijkstra algorithm examines an edge, it removes an edge from the pool, thereby reducing the number of constraints. It's not horribly useful terminology, but think how cool you'll sound saying it.


2 Answers

Relaxation step:

  • You have two nodes, u and v
  • For every node, you have a tentative distance from the source node (for all nodes except for the source, it starts at positive infinity and it only decreases up to reaching its minimum).

The relaxation step basically is asking this:

  • I already know that I can reach v with some path of distance dist[v]. Could I improve on this by going to v through u instead? (where the distance of the latter would be dist[u] + weight(u, v))

Graphically:

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

You know some path s~>v which has distance dist[v], and you know some path s~>u which has distance dist[u]. If dist[u] + weight(u, v) < dist[v], then the path s~>u->v is shorter than s~>v, so you'd better use that one!

(I write a~>b to mean a path of any length from a to b, while a->b I mean a direct single edge from a to b).

You may also want to check this lecture: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed17.htm

like image 157
Dimitris Andreou Avatar answered Nov 13 '22 21:11

Dimitris Andreou


One of the meanings of the english word "relaxation" is decreasing something. Because at lines 14,15 and 16 you are essentially checking if you can decrease(optimize) the currently computed distance, I guess that's why it is called "relaxation condition".

like image 41
Petar Minchev Avatar answered Nov 13 '22 23:11

Petar Minchev