Вопрос по graph-theory, graph-algorithm, algorithm – Релаксация ребра в алгоритме Дейкстры

32

Что значитrelaxation of an edge значит в контексте теории графов? Я сталкивался с этим, изучая алгоритм Дейкстры для кратчайшего пути из одного источника.

Ваш Ответ

4   ответа
39

Здесь & APOS; s хорошее описание алгоритма, который также объясняет понятие релаксации.

The notion of "relaxation" comes from an analogy between the estimate of the shortest path and the length of a helical tension spring, which is not designed for compression. Initially, the cost of the shortest path is an overestimate, likened to a stretched out spring. As shorter paths are found, the estimated cost is lowered, and the spring is relaxed. Eventually, the shortest path, if one exists, is found and the spring has been relaxed to its resting length.

Есть ли причина говорить, что EDGE ослаблен, а не путь к узлу v. Почему & quot; EDGE & quot; расслабление, а не «путь» отдых
8

которую вы можете найти и в других алгоритмах кратчайшего пути) пытается снизить стоимость перехода в вершину с помощью другой вершины.

Вы вычисляете расстояния от начальной вершины, скажем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).

22

ти всех вершин, соединенных с вершиной v, если эти затраты будут улучшены путем включения пути через v.

0

E где w (u, v) = 10 тогда, если, добавив третью вершину между ними, как w (u, y) = 1 и w (y, v) = 3, теперь мы найдем путь между u и v с весом 1 + 3 = 4 & lt; 10. Теперь мы рассмотрим второй путь как самый короткий, который (u, y, v), и проигнорируем первый, это релаксация.

Похожие вопросы