使用K个反向边的图形中所有最短路径 [英] All shortest paths in a graph using K reverse edges

问题描述

假设我有一个有向图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 ₀ 到 G _K ，然后在 G u _i > 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, G₀ to G_K, and then connect a vertex u_i in G_i to a vertex v_i+1 in G_i+1 if there is an edge from v to u in G.

s ₀ 在 G _{0 到 G i 中的 t i 表示从 G 中的 s 到 t 的路径，该路径使用 i 反向边，其中 i 最多为 K 。}

A path from s₀ in G₀ to t_i in G_i 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个反向边的图形中所有最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！