给定加权无向图G和两个节点U,V以获得最短路径.如何获得从U到V的最短路径,使用偶数个边缘(如果可能的话)？
我在网上发现了一些文章,说原始图表上的修改是必要的.但我无法理解如何做到这一点.
有一些很好的材料可以研究这个问题吗？
您需要构建一个中间图并在该图上运行 Dijkstra。
给定一个图G = (V, E)，创建一个新图G' = (V', E')，具有V'一组新的顶点v_even，对于中v_odd的每个顶点和该组顶点如下：如果是 中的边，则和是 中的边，具有相同的权重。vVE'(u, v)G(u_odd, v_even)(u_even, v_odd)G'
显然，新图的边和顶点数量是原始图的两倍。
s现在，如果您想找到和t之间的最短路径G，只需运行 Dijkstra's on即可找到和G'之间的最短路径。s_event_even
运行时间依然O(|V| log |E|)。