algorithm - 具有锁定和未锁定边的无向图中的最小路径

Question

给定一个具有正权重的无向图，有两种边：锁定边和解锁边。确定给定边是锁定边还是解锁边需要 O(1)。

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

2. 对于给定的两个顶点s，t和一个正数k = O(1)，我怎样才能找到s和t之间包含恰好 k个锁定边的最短路径？

我不确定如何在该图上运行 Dijkstra 算法以找到给定顶点之间的最短路径，以及如何将无向图转换为有向图。

Answer 1

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