带锁边和不带锁边的无向图的最小路

Question

给定一个带正权的无向图，有2种边：锁定边和未锁定边。确定给定边沿是锁定边沿还是未锁定边沿需要O(1)。

>

对于给定的两个顶点s，t和一个正数k=O(1)，我如何找到s和t之间最多包含k条锁定边的最短路径？

对于给定的两个顶点s，t和一个正数k=O(1),我如何找到s和t之间恰好包含k条锁定边的最短路径？

我不知道如何在这个图上运行Dijkstra算法来找到给定顶点之间的最短路径，以及如何将无向图转化为有向图。

Answer 1

您可以通过获取图的k副本来解决这两个问题，例如G_0，...，G_k，并修改每个图，使G_i中的锁定边vw变成从G_i中的u到G_{i+1}中的v以及从G_i中的v到G_{i+1}中的u的边。然后您可以从您的根在G_0中执行单源最短路径。第二个查询是通过读取G_k中到目标的距离来解决的，而第一个查询是通过读取任何G_i中到目标的最小距离来解决的。