Я хотел бы реализовать кратчайшие пары реберно-непересекающихся путей Суурбалла и Тарьяна для мультиграфов в интерпретации Банерджи и др. (http://web.cs.iastate.edu/~pavan/papers/short.pdf,, полагаясь только в разделе 3).
Что касается простых графов , этот алгоритм может быть определен для G = (V, E) простого графа, имеющего источник s и неотрицательные ребра c (u, v) следующим образом:
(1) Построить дерево кратчайших путей T с корнем в s для G , используя алгоритм Дейкстры.
(2) Уменьшить стоимость по всем ребрам (a, b) как c '(a, b) = c (a, b) + d (a) -d (b). ) , где d (a) - расстояние от вершины a до вершины s .
(3) Создайте вспомогательный граф G '= (V', E ') следующим образом:
(3.1) установлено V '= V и E' = пусто,
(3.2) для каждого нетривого ребра (a, b) E \ T :
(3.2.1) определяет V * как набор узлов на пути между a и b в T , за исключением для b ,
(3.2.2) для каждого v ' из V *: набор E' = E 'U {(v', b)} и * * тысяча семьдесят-одна с '(V', Ь) = C '(а, б) * * тысяча семьдесят две.
(4) Построить дерево кратчайших путей T ' с корнем в s для G' , взвешенных с помощью функции c ', используя алгоритм Дейкстры.
(5) Сохраните предшественник каждой вершины x в T ' как q (x) и хвост нетронутого ребра в G , который вызвал вставку (q (x), x) в G '.
(6) Создайте пары непересекающихся с ребром путей для каждого v из V следующим образом:
(6.1) Отметьте все вершины в кратчайшем пути от v до s в G .
(6.2) Генерация путей за две итерации шага Обход , приведенного ниже. В каждой итерации генерируется один путь из самых коротких пар.
Обход: Определите x = v , путь должен быть пустым и повторяйте следующие шаги до x = s . Если отмечен x , снимите его и добавьте (p (x), x) к пути, или добавьте (y, x) к пути где y является родителем x в T .
Не могли бы вы помочь мне, как переформулировать алгоритм для мультиграфов? Я думаю, что G ', p (), q () и Обход из Раздела 3 в статье Банерджи и др. должны быть как-то изменены, но я не знаю, как .