在动态有向图中寻找最小循环路径

Question

我最近在今年早些时候遇到了来自Spotify黑客挑战的this (Edit: Problem A)有趣的问题，这个问题涉及确定火车卡车路口的切换，以便将列车返回到起点。火车必须朝着它的方向到达，火车不能在轨道上颠倒。

据我所知，问题可以建模为一个无向（？）图，我们必须从某个顶点找到最短周期，或者检测出没有这样的周期存在。然而，有趣的部分是，对于一个顶点v，与v相邻的顶点依赖于对v取的路径，所以从某种意义上说，图可以被认为是有向的，尽管这个方向是路径依赖的。

我的第一个想法是将每个节点建模为3个单独的顶点A，B和C，其中A和B都是A和B，然后使用宽度优先搜索来构建搜索树直到我们找到了原始的顶点，但是由于上面的警告，这是复杂的，即给定顶点的邻接点取决于我们访问的前一个顶点。这意味着在我们的BFS树中，节点可以有多个父节点。

显然，一个简单的BFS搜索不足以解决这个问题。我知道存在用于检测图形中的周期的算法。一种方法可能是检测所有的周期，然后在每个周期检测路径是否有效。 （即不反转方向）

其他人对解决此问题的方法有任何见解吗？

更新： 我遵循@Karussell在评论中提出的方法。

Here is my solution on github.

诀窍是使用基于边缘的图形，而不是传统的基于顶点的曲线图的情况进行建模。比赛中提供的输入文件可以方便地按边缘指定，因此可以轻松使用此文件构建基于边缘的图形。

程序使用了两个重要的类：Road和Solver。道路有两个整数字段，j1和j2。 j1表示源结，j2表示目标结。每条路都是单向的，这意味着你只能从j1行驶到j2。每条道路还包括相邻道路的链接列表和父路。 Road类还包含静态方法，用于在输入文件中使用的字符串和表示每个交叉点处的A，B和C点的整数索引之间进行转换。

对于输入文件中的每个条目，我们为两个路口之间的每个方向添加两条道路到一个HashMap，一条道路。我们现在列出了在路口之间运行的所有道路。我们只需要通过A，B和C开关将交叉口连接在一起。如果一条公路在Junction.A结束，我们将查找在Junction.B和Junction.C处开始的道路，并将这些道路作为邻接点。 buildGraph（）函数返回其目标交叉点（j2）为“1A”==索引0的Road。

此时，我们的图形被构造。要找到最短路径，我简单地使用BFS来遍历图。我们将根标记为未标记，并开始排列根的邻接关系。如果我们找到目标路口为“1A”（索引0）的道路，那么我们已经找到了通过起点的最短周期。一旦我们使用每条道路的父属性重建路径，根据问题的要求适当地设置交换机是一件小事。

感谢Karussell提出这种方法。如果您想以简短的解释将您的评论置于答案中，我会接受它。感谢@Origin，以及。我必须承认，我没有完全遵循你答案的逻辑，但这当然不是说它不正确。如果有人使用你的解决方案解决了这个问题，我会很乐意看到它。

Answer 1

正如我的评论建议：我认为你可以通过edge based graph或通过an improvement解决这个问题，这或多或少是一个'增强'节点的基础图。

详情：

• 你的情况类似，把路网限制。如果您为每个（定向！）街道创建一个节点并根据允许的转弯连接节点，则可以对这些节点进行建模。
• 因此，不仅要存储您当前位置的位置，还要存储方向和可能的更多'情况'。为了尽可能使相同的180°转弯位置与您当前的状态不同。

相反造型的“状态”（这是导演！）到图形，你还可以分配可能的结果每一个结 - 现在的算法需要更加聪明，需要每个结点来决定取决于做什么在你以前的状态（包括方向）上。我认为，这是'增强型'基于节点的图形的主要思想，应该减少内存密集度（在你的情况下不那么重要）。

Answer 2

一种可能的方法：首先建立某种图形来建模所有连接（图G）。然后构造另一个图，我们将在其中找到循环（图H）。对于G中的每个节点A，我们将向图H添加一个节点。每个A节点也有2个输出边（对于图G中的B和C节点）。在H中，这些边将转到在G中遇到的下一个A节点。例如，对应于ID为3的交换机的A节点的H中的A节点将具有到节点9和节点6的传出边缘， H.每条边的权重是在该路由上传递的交换机的数量（包括启动开关）。

这将产生一个图，我们可以在其中生长一个前向最短路径树。如果我们再次启动，循环将完成。

关键是，如果在A->方向上遍历，交换机只是一个决策点。没有必要对后向建模，因为这只会使搜索复杂化。

编辑：一些更多的澄清

问题由从A确定A（再次）的最短路径。这里最短的定义是通过的开关数量。这将用于基于Dijkstra的搜索算法。我们基本上是要在图H上做Dijkstra，其中边的成本等于该边的开关数。

在H图中，我们将为每个开关都有一个节点。每个节点将有2个传出边缘，对应于可以采用的2条路径（B和C方向）。 H中的边将对应于原始图中2个节点之间的整个路径。对于该问题的说明的例子中，我们得到如下：

的节点对应于切换1：

• 1个输出链路到节点2，权重2，对应于离开开关时拍摄的C 方向1.权重为2，因为如果我们从A1-> C1-> C3-> A3-> A2传递开关1和开关3，则对应于采取B方向的1个传出链接到节点3，权重2

对应于开关2的节点：

• 1个输出链路到节点6，权重2，对应于服用B方向
• 没有第二连杆的C方向是死路

的节点对应于开关3：

• 1个输出链路到节点6，权重2，对应于取C方向
• 1输出链路到节点9，配重3，对应采取B方向和通过开关3,7和8

等等每个开关。这产生了具有10个节点的图形，每个节点具有至多2个有向边缘。

现在我们可以开始构建我们的Dijkstra树了。我们从节点1开始，并有2个可能的方向，B和C.我们把这些放在优先队列中。然后，队列中包含[节点2，权重2]和[节点3，权重2]，因为我们可以在通过2个交换机之后到达交换机2的A入口，并且在通过2个交换机之后通过交换机3的A入口。然后，我们继续通过取从队列中最低重量条目的搜索：

• [节点2，重量2]：仅B方向拿，这样就把[节点6，重量4]在队列
• [节点3，权重2]：取2个方向，因此在队列中添加[节点6，权重4]和[节点9权重5]。
• [节点6，重量4]：2点的方向可能的，添加[节点4，重量5]和[节点8，体重8]到队列]
• [节点9，重量5]：仅C方向，添加[节点10，权重6]
• [节点4，权重5]：对于C方向添加[节点5，权重7]，对于B方向添加[节点1，权重9]
• [节点10，权重6]：为C方向添加[节点1，权重8]，B方向添加[节点1，权重10]
• [节点5，权重7]：添加[节点1，权重11]和[node 8，weight 10]
• [node 8，weight 8]：add [node 7，weight 9]
• [节点1，重8]：我们发现我们回来的路上，所以我们可以停止

（错误是可能的，我只是用手工做这个）

算法然后用停止一个周期的最终长度为8。确定后续路径只是在解决它们并解开路径时维护节点的父指针。

我们可以使用Dijkstra，因为H中的每个节点都对应于在正确的方向上遍历原始节点（G）。 H中的每个节点都可以用Dijkstra方式来解决，因此算法的复杂度仅限于Dijkstra（可以处理交换机数量的100k上限）的算法。