给定有向加权图 G=(V,E)。
没有负加权边。
每条边都是彩色的(黑色或黄色)。
我需要找到一个算法来找到给定 s ∈ V 的最短路径，而每条路径都必须遵循以下规则:color(vi,vi+1)=color(vi+3,vi+4), ∀i :1 ≤ i ≤ k-4 而路径为v1 → ... → vk。 该算法需要在 O(|V|+|E|log(|V|)) 内。
最佳答案
提示:尝试修改 Dijkstra 算法以存储两个不同的优先级队列:一个包含从起始节点到以黄色边结束的目标节点的路径成本，以及从起始节点开始的路径成本到以黑色边缘结束的目标节点。然后，更新逻辑以找到下一个节点以选择将两个队列考虑在内，并更改减少键逻辑以确保您使用正确的信息更新正确的队列。这可以通过普通 Dijkstra 算法的常数因子开销来完成，因此需要时间 O(|E| + |V| log |V|)。
希望这对您有所帮助!
关于algorithm - 具有黄色和黑色边缘的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14127039/