Все кратчайшие пути в графе с использованием K обратных ребер

Question

Допустим, у меня есть ориентированный граф G (V, E) с положительными целочисленными весами на его ребрах. Что мне нужно сделать, это найти кратчайшие пути между всеми вершинами, используя не более K (целых) обратных ребер. Что я имею в видуто есть: если мы находимся на ребре u и существует только направленное ребро от v к u, мы можем использовать его, если мы не использовали K обратных ребер для этого пути. Это должно быть реализовано в C ++ и дать самое короткоепути в результате.

Я думал о запуске dijkstra V раз (что-то вроде алгоритма Джонсона), но я не уверен, как воспользоваться преимуществом свойства обратного края. Есть идеи?

Answer 1

Общий подход к таким проблемам обычно описывается как «многоуровневое».Вы (концептуально) делаете K + 1 копию графика, G ₀ до G _K , а затем соединить вершину u _i в G _i к вершине v _{i + 1} in G _{i + 1} , еслиесть грань от v до u в G .

Путь от s ₀ в G ₀ до т _i в G _i затем представляет путь от s до t в G , который использует i обратных ребер, где i - самое большее K .

Вы можете просто использовать алгоритм Дейкстры на этом новом многоуровневом графе.

Когда вы привыкнете к этому, вы можетеПодумайте об этом еще проще: вы просто используете алгоритм Дейкстры, но вместо того, чтобы иметь состояния в очереди, такие как [достигнут v , со стоимостью c ], вы используете состояния, такие как [достигнут v , со стоимостью c , используя i обратные края].Часто, когда мы используем Дейкстру в реальной жизни, фактический граф не дается, поэтому он помогает воспринимать его как поиск по состояниям и их переходам.