Дан взвешенный ориентированный граф G = (V, E). Нужно найти кратчайшие пути из s до всех остальных вершин. Известно, что веса рёбер кратчайшего пути из s в любую вершину v образуют битоническую последовательность.
Битоническая последовательность вначале монотонно возрастает, а затем монотонно убывает, или можно путём сдвига получить такую.
Какой есть эффективный алгоритм решения данной задачи? Я как понимаю, что-нибудь лучше чем Беллман-Форд и с использованием свойства битонизма.
Ещё интересует вопрос. Необходимо найти кратчайшие простые пути в взвешенном ориентированном графе из вершины s до всех остальных. Граф может содержать отрицательные циклы. Как оптимально решается эта задача? Увеличением весов на константу, так чтобы не было отрицательных рёбер и последующий алгоритм Дейкстры или Беллмана-Форда?
Произведите релаксацию всех ребер ровно V (число вершин) раз. Если при исполнении последней итерации длина кратчайшего пути до какой-либо вершины уменьшилась, значит в графе есть цикл отрицательного веса, достижимый из вершины S. Это касательно второго вопроса.
Можно найти кратчайшие пути из вершины, которые являются возрастающими и отдельно найти кратчайшие пути, являющиеся убывающими. Например, алгоритмом Дейкстры. Затем для каждой вершины найти все вершины пересечения кратчайшего возрастающего и убывающего пути. Среди путей вида "возрастающий до точки пересечения, затем убывающий" найти минимальный. Это по первому вопросу.
Второй вопрос Вы поняли неверно.
По поводу первого, к сожалению, тоже не очень понятно. Последовательность { - 5, - 1, 2, - 1, - 5}, очевидно тоже является битонической.
Я подумал, кратчайший путь определяет последовательность номеров вершин в нем.
Моя вина. Исправил.
Ограничения какие? Можно добавить в состояние вес ребра, по которому пришли и находить "возрастающие" и "убывающие" пути и перебирать промежуточную вершину.
Битонический кратчайший путь — это асфальт