Улучшение Bellman-Ford до линейного времени выполнения
В алгоритме Джонсона он использует Беллмана-Форда для преобразования графиков с отрицательными весами ребер (без отрицательных циклов) в граф с такими же кратчайшими путями, но все веса ребер неотрицательны - за O(mn) времени.
Предположим, нам дан DAG. Как мы могли бы использовать альтернативный метод для преобразования DAG в другой граф с теми же самыми короткими путями, но в линейном времени, в отличие от предыдущего времени O(mn).
Я предполагаю, что мы могли бы изменить Беллмана-Форда во время выполнения алгоритма Джонсона, однако я не уверен, как сделать его линейным. По сути, как мы можем найти способ перевесить все ребра графа, чтобы они были неотрицательными за линейное O(n) время?