Дан взвешенный ориентированный граф G = (V, E). Нужно найти кратчайшие пути из s до всех остальных вершин. Известно, что веса рёбер кратчайшего пути из s в любую вершину v образуют битоническую последовательность.

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

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

Ещё интересует вопрос. Необходимо найти кратчайшие простые пути в взвешенном ориентированном графе из вершины s до всех остальных. Граф может содержать отрицательные циклы. Как оптимально решается эта задача? Увеличением весов на константу, так чтобы не было отрицательных рёбер и последующий алгоритм Дейкстры или Беллмана-Форда?