Релаксация ребра в алгоритме Дейкстры

Ответ 1

Вот хорошее описание Алгоритма, которое также объясняет понятие релаксации.

Понятие "расслабления" происходит из аналогии между оценкой кратчайшего пути и длины спирального натяжения spring, который не предназначен для сжатия. Первоначально стоимость самого короткого путь завышен, сравненный с растянутым spring. Чем короче пути найдены, сметная стоимость снижена, а spring - расслаблены. В конце концов, найден самый короткий путь, если он существует, и spring был ослаблен до длины покоя.

Ответ 2

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

Край релаксации.

Ослабить ребро 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/