Tom*_*God 2 algorithm graph-theory graph graph-algorithm data-structures
给定具有正权重的无向图,有两种边:锁定边和未锁定边.确定给定边缘是锁定边缘还是解锁边缘需要O(1).
对于给定的两个顶点s,t和正数k = O(1),如何找到s和t之间最短路径,其中包含最多 k个锁定边缘？
对于给定的两个顶点s,t和一个正数k = O(1),如何找到包含正好k个锁定边的s和t之间的最短路径？
我不知道我怎么能在这个图运行Dijkstra算法找出给定顶点之间的最短路径,以及如何改造无向图,为指导之一.
您可以通过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到目标的最小距离来解决的.