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

Ответ 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 кратчайших путей -th могут иметь общие ребра и подпуть (путь от источника до любых промежуточных узлов в пределах маршрута) из кратчайшего пути (k-1) -th. Затем вы должны выбрать (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

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

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

=====

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

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

=====

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

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

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

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

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

=====

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

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

=====

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

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