algorithm - 最小权重完美匹配的最短偶数路径

Question

给定一个边加权无向图和两个顶点 s 和 t，权重是非负的。Shortest Even Path Problem是寻找一条边数为偶数且总权重尽可能小的s,t路径P。如何将最短路径问题化简为最小权完美匹配问题

Answer 1

从给定的图开始，想象将节点涂成蓝色，并将其命名为 G_blue。它有节点，包括 s_blue 和 t_blue，以及像 a_blue <-> b_blue 这样的无向边.

制作一个图的副本，将其节点涂成绿色并将其命名为 G_green。

现在重新连接所有的边，这样 a_blue<->b_blue 和 a_green<->b _green (具有相同的权重)变成 a_blue<->b_green 和 a_green<->b_蓝色(具有相同的权重)。

在这个组合图中，每条边都在蓝色节点和绿色节点之间，因此每条路径都在蓝色和绿色之间交替。因此，每条从 s_blue 开始的步数为偶数的路径都将以绿色节点结束。

现在在这个组合图上，寻找从 s_blue 到 t_green 的最小权重路径。

最后，去掉下标。