algorithm - 黄色和黑色边缘的最短路径

Question

给定有向加权图 G=(V,E)。
没有负加权边缘。
每个边缘都有颜色（黑色或黄色）。

我需要找到一种算法来找到给定 s ∈ V 的最短路径，而每条路径都必须遵循以下规则：color(vi _, vi ₊₁ )=color(vi ₊₃ ,vi ₊₄ ), ∀i :1 ≤ i ≤ k-4 而路径是 v ₁ → ... → v _k。该算法需要在 O(|V|+|E|log(|V|)) 中。

Answer 1

作为提示：尝试修改 Dijkstra 的算法以存储两个不同的优先级队列：一个包含从起始节点到以黄色边缘结束的目标节点的路径成本，以及从起始节点到目的地的路径成本以黑边结束的节点。然后，更新逻辑以找到下一个节点以选择考虑两个队列，并更改减少键逻辑以确保您使用正确的信息更新正确的队列。这可以通过普通 Dijkstra 算法的常数因子开销来完成，因此需要时间 O(|E| + |V| log |V|)。

希望这可以帮助！

Answer 2

您可以像 templatetypedef 建议的那样修改 Dijkstra 的算法，或者修改图形以适应约束。

您可以使用DFA识别颜色约束，并将其与您的加权图结合以获得可以应用未修改的 Dijkstra 的图，从而实现典型的 Dijkstra 运行时。

约束的确切开销取决于 DFA 的大小，但它是恒定的，因为 DFA 不依赖于输入。