假设我有一个有向图G(V,E)在其边缘具有正整数权重,我需要做的是找到最多使用K(整数)个反向边缘的所有顶点之间的最短路径。这就是:如果我们在u边,并且从v到u只有一条有向边,我们可以使用它,只要我们没有为此路径使用K个反向边就必须使用C ++并给出最短的边
Let's say i have a directed graph G(V,E) with positive integer weights at it's edges.What i need to do is find the shortest paths between all vertices using at most K(integer) reverse edges.What i mean by that is:If we are at edge u and there is only a directed edge from v to u we can use it as long as we have not used K reverse edges for this path.This has to be implemented in C++ and give the shortest paths as a result.
我考虑过运行dijkstra V次(类似于Johnson的算法),但是我不确定如何利用反向边缘属性。 ?
I thought about running dijkstra V times(something like Johnson's algorithm)but i am not sure how to take advantage of the reverse edge property.Any ideas?
推荐答案解决此类问题的常用方法通常称为分层。您(从概念上)复制图的 K +1个副本,从 G 0 到 G K ,然后在 G i 到 G 中的顶点 v i +1 如果 G 中从 v 到 u 有一条边,则 i +1 。
The common approach to problems like this is usually described as "layering". You (conceptually) make K+1 copies of the graph, G0 to GK, and then connect a vertex ui in Gi to a vertex vi+1 in Gi+1 if there is an edge from v to u in G.
s 0 在 G 0 到 G i 中的 t i 表示从 G 中的 s 到 t 的路径,该路径使用 i 反向边,其中 i 最多为 K 。
A path from s0 in G0 to ti in Gi then represents a path from s to t in G that uses i reverse edges, where i is at most K.
您可以在这个新的分层图中使用Dijkstra的算法。
You can just use Dijkstra's algorithm on this new layered graph.
当您习惯了这一点时,您可以用一种更简单的方式来思考:您只使用Dijkstra的算法,而不是像[reached v 成本 c ],则您可以使用[reached v c ,已使用 i 反向边缘]。通常,当我们在现实生活中使用Dijkstra的图时,没有给出实际的图,因此将其视为对状态及其转换的搜索会有所帮助。
When you get used to this you can think about it in an even simpler way: you just use Dijkstra's algorithm, but instead of having states in the queue like [reached v, with cost c], you use states like [reached v, with cost c, having used i reverse edges]. Often, when we use Dijkstra's in real life, there is no actual graph given, so it helps to think of it as a search through states and their transitions.
更多推荐
使用K个反向边的图形中所有最短路径
发布评论