Какова цель посещаемого набора в Дейкстре?

На странице Википедии для алгоритма Дейкстры они помечают посещенные узлы, чтобы они больше не добавлялись в очередь. Однако, если узел посещается, то не может быть расстояния до этого узла, которое короче, так что проверка alt < dist[v] уже учитывает посещенные узлы? Может быть, я что-то недопонимаю в посещаемом наборе?

for each neighbor v of u:   
      alt := dist[u] + dist_between(u, v);          // accumulate shortest dist from source
      if alt < dist[v] && !visited[v]:                                 
          dist[v]  := alt;                          // keep the shortest dist from src to v
          previous[v]  := u;
          insert v into Q;                          // Add unvisited v into the Q to be processed
      end if
  end for
2 4
algorithm shortest-path dijkstra

2 ответа:

На самом деле есть 2 набора, которые вы должны рассмотреть:

  • посещаемое множество
  • набор очередей

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

набор очередей содержит неисследованные вершины, расположенные в порядке наименьших расстояний от начала вершина

В зависимости от плотности графа каждая вершина может быть частью более чем одного ребра. обратите внимание, что ребро-это наименьший компонент, соединяющий вершину с другой вершиной.. Следовательно, это подразумевает возможность наличия более чем одной вершины с ребром к текущей вершине.

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

Причина alt < dist[v] заключается в том, что можно столкнуться с вершиной, которая уже находится в очереди более одного раза, поэтому каждый раз, когда она встречается, вы должны убедиться, что перед редактированием ее расстояния до исходной вершины, ее текущее расстояние больше, чем новое расстояние, которое вы хотите ей назначить. (alt < dist[v]) и он не обрабатывается как посещенный (!visited[v])

  • Алгоритм Дейкстры дает гарантию, что как только узел помечен как visited, значение расстояния этого узла является самым коротким до источника. Если узел помечен как посещаемый, это не означает, что расстояние до источника от этого узла является самым коротким расстоянием по сравнению с расстоянием от источника до любого другого узла. Это означает, что цель алгоритма Дейкстры была удовлетворена для этого узел; который состоит в том, что он в настоящее время хранит наименьшее расстояние от источника до себя.

  • Если вы полностью хотите отказаться от проверки посещений, то вы можете сделать следующее: Как только вы отметите узел как посещенный, вы пройдете через все ребра, связанные с этим узлом, и удалите их. Это гарантирует, что все будущие обрабатываемые узлы не имеют ребра, которое соединяется с любым узлом, помеченным как посещенный. Однако, поскольку граф представлен с помощью представления списка смежности, переход к этому варианту будет дорогостоящим с точки зрения времени; и в зависимости от того, насколько плотен график, вам было бы лучше просто иметь посещенный набор. Но если вы представляете свой график с помощью матрицы смежности, то преимущество этого состоит в том, что проверка будет стоить только O(N) времени. Однако матрица смежности использует N2 пространство vs N пространство списка смежности, вы будете платить цену за это с точки зрения памяти, которая может быть или не быть настолько плохой в зависимости от размер графика.

Как только вы поймете Дийкстру, вы увидите, что все, что сделано в коде, необходимо для получения правильных результатов.
5

Да, вы правы. Нет никакой необходимости в посещаемом векторе.

Если узел посещается, то не может существовать расстояния до этого узла, которое короче, поэтому, как вы сказали, достаточно проверить alt < dist[v].

Взгляните сюда:

1