Алгоритм Эппштейна и алгоритм Йена для k кратчайших путей

Question

Я пытаюсь понять, как именно работают эти алгоритмы, но я не смог найти простого объяснения. Я был бы очень признателен, если бы кто-то мог предоставить или указать мне описание этих алгоритмов, которое легче понять, чем описание в оригинальных статьях. Благодарю.

Answer 1

Прежде всего, позвольте мне предоставить вам ссылки на газеты, о которых вы говорили.

Статья Эппштейна: Д. Эппштейн, "Нахождение k кратчайших путей", SIAM J. Comput., Vol. 28, нет. 2, с.652–673, февраль 1999 г.

Статья Йена: JY Йен, "Нахождение K кратчайших циклов без петель в сети", Management Science, vol. 17, нет. 11, с. 712–716, 1971.

Вот мое объяснение алгоритма Йена:

Алгоритм Йена использует два списка, то есть список A (постоянные кратчайшие пути от источника к месту назначения - в хронологическом порядке) и список B (предварительные / возможные кратчайшие пути). Сначала вы должны найти 1-й кратчайший путь от источника к месту назначения с помощью любого подходящего алгоритма кратчайшего пути (например, Дейкстры). Затем Йен использует идею о том, что k-е кратчайшие пути могут иметь общие ребра и подпуть (путь от источника к любым промежуточным узлам в пределах маршрута) от (k-1)-го кратчайшего пути. Затем вы должны выбрать (k-1) кратчайший путь и сделать каждый узел на маршруте недоступным по очереди, т. Е. Стереть определенный край, который идет к узлу в пределах маршрута. Когда узел недоступен, найдите кратчайший путь от предыдущего узла к месту назначения. Затем у вас есть новый маршрут, который создается путем добавления общего подпути (от источника к предыдущему узлу недоступного узла) и добавления нового кратчайшего пути от предыдущего узла к месту назначения. Этот маршрут затем добавляется в список B, при условии, что он не появлялся в списке A или списке B ранее. После повторения этого для всех узлов в маршруте, вы должны найти кратчайший маршрут в списке B и переместить его в список A. Вам просто нужно повторить этот процесс для количества Ks, которые у вас есть.

Этот алгоритм имеет вычислительную сложность O(kn^3). Пожалуйста, прочитайте статью для более подробной информации.

Алгоритм выглядит следующим образом:

G = Adjacent Matrix of the Network
Initialize:
A_1 = shortest-path from source to destination
Glocal ← Local copy of G
for k = 2 → K do
 for i = 1 → [len(A_(k−1) ) − 1] do
  Current Node ← A_(k−1) [i]
  Ri ← Sub-path (root) from source till current node in A_(k−1)
  for j = 1 → k − 1 do
   Rj ← Sub-path (root) from source till current node in A_j
   if Ri == Rj then
    Next Node ← Aj [i+1]
    Glocal(Current Node, Next Node) ← infinity
    Current Node ← unreachable
   end if
  end for
  Si ← Shortest-path from current node till destination
  Bi ← Ri + Si
 end for 
 A_k ← Shortest-path amongst all paths in B
 Restore original graph: Glocal ← Local copy of G
end for

К сожалению, я не использовал метод Эппштейна, поскольку алгоритм Йена был оптимальным для моей задачи.

Надеюсь это поможет. Приветствия.

=====

Редактировать:

Пожалуйста, посмотрите на запись в Википедии. Это хороший пример.

=====

Редактировать:

Я нашел несколько реализаций в C. Ссылки следующие:

Реализация Eppstein и график загрузки для Eppstein.

Если вам интересно, есть ленивая версия Eppstein. Ссылка следующая:

Ленивый Эппштейн, Хименес и Марзал

=====

Редактировать:

Просто еще одна ссылка. Этот содержит несколько реализаций (C / C++).

=====

Редактировать:

Я нашел хорошее объяснение алгоритма Эппштейна.