кратчайший путь к минимальному весу, идеальное соответствие

Question

Учитывая взвешенный по ребру ненаправленный граф и две вершины s и t, веса неотрицательны.Кратчайший четный путь Задача состоит в том, чтобы найти s, t-путь P, имеющий четное число ребер, общий вес которых как можно меньше.Как уменьшить проблему кратчайшего четного пути до минимальной проблемы с идеальным соответствием веса

Answer 1

Начните с данного графика, представьте, что закрасили узлы синим цветом и назовите его G _blue .Он имеет узлы, включая s _blue и t _blue , и ненаправленные ребра, такие как _blue <-> b _blue .

Сделайте копию графика, закрасьте его узлы зеленым и назовите его G _{зеленый} .

Теперь заново соедините все ребра, чтобы _синий <-> b _синий и _{зеленый} <-> b _{зеленый} (имеющие одинаковый вес) становятся _синим <-> b _{зеленый} и _{зеленый} <-> b _синий (с одинаковыми весами).

В этом комбинированном графике каждое ребро находится междусиний узел и зеленый узел, поэтому каждый путь чередуется между синим и зеленым.Таким образом, каждый путь из s _blue , имеющий четное число шагов, заканчивается зеленым узлом.

Теперь на этом комбинированном графике ищите путь минимального веса из s _синий до t _{зеленый} .

Наконец, удалите индексы.