Кратчайшие пути, запрещающие каждый край

Я был бы признателен за любые указания или термины, которые могли бы привести меня в правильном направлении.

У нас есть ориентированный граф и длины для каждого ребра которое можно считать положительным. Существует специальный начальный узел и конечный узел .$G=(V,E)$$l_{ij}$$ij$$s$$t$

Для каждого ребра мы бы хотели вычислить длину кратчайшего пути от до , который не использует ребро .$ij$$s$$t$$ij$

Простой алгоритм перебора - это запуск алгоритма кратчайшего пути для каждого ребра, каждый раз удаляя разные ребра из исходного графа. Есть ли более эффективный алгоритм, который использует тот факт, что в этом алгоритме грубой силы происходит много повторных вычислений?

Заранее спасибо.

Проблема, которую вы упоминаете, называется «пути замены». Вот несколько ссылок:

1. Готильф и Левенштейн. Усовершенствованные алгоритмы для k простых кратчайших путей и задач замены путей. Inf. Proc. Letters, 109 (7): 352–355, 2009. В этой статье приведен самый быстрый на сегодняшний день точный алгоритм для задачи замены путей, выполняемый за время в графах с узлами. и ребер.$O(mn+n^2\log\log n)$$n$$m$
2. А. Бернштейн. Почти оптимальный алгоритм для аппроксимации путей замены и k кратчайших простых путей в общих графах. В учеб. SODA, стр. 742–755, 2010. Эта статья удивительным образом дает схему аппроксимации квазилинейного времени для задачи.
3. J. Hershberger, S. Suri и A. Bhosle. О сложности некоторых кратчайших путей. В учеб. STACS, стр. 343–354, 2003. Эта статья показывает, что любой алгоритм сравнения путей, решающий проблему замены, в точности должен занимать как минимум время.$\Omega(m\sqrt{n})$
4. В. Васильевская В., Р. Уильямс. Субкубические эквивалентности между задачами пути, матрицы и треугольника. В учеб. FOCS, стр. 645-654, 2010. Мы показываем, что если вы получите алгоритм точного времени для путей замены для любой константы , то это можно преобразовать в алгоритм времени для всех пар кратчайших путей для константы . Такой действительно субкубический алгоритм для всех пар кратчайших путей является давней открытой проблемой.$O(n^{3-\varepsilon})$$\varepsilon>0$$O(n^{3-\varepsilon'})$$\varepsilon'>0$
5. О. Вейман, Р. Юстер. Пути замены с помощью быстрого умножения матриц. В учеб. ФОКС, стр. 655-662, 2010. и В. Василевская В. Ускоренные пути замены. В учеб. SODA, стр. 1337-1346, 2011. В этих работах показано, как использовать быстрое умножение матриц для нахождения путей замены в графах с целочисленными весами ребер в интервале . В последней статье дается самая известная на данный момент среда выполнения, .$\{-M,\ldots, M\}$$\tilde{O}(Mn^\omega)$

Если вы хотите связать с каждым ребром длину кратчайшего пути между и , вы можете начать с вычисления кратчайшего пути во всем графе и связать его с каждым ребром не по кратчайшему пути, который вы только что вычислили, для длины текущего кратчайший путь. После этого у вас осталось не более ребер, для которых вы не знаете ответ.$s$$t$$n-1$