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