算法:最小路径交替颜色

Question

设 G 是一个有向加权图，节点为黑色或白色，所有权重均为非负数。没有指定其他信息——没有开始或结束顶点。

我需要找到一条权重最小的路径(不一定简单)，它至少要交替颜色 n 次。我的第一个想法是运行 Kosaraju 的算法来获取组件图，然后找到组件之间的最小路径。然后您可以选择入度为零的节点，因为这些节点的颜色变化至少与从入度为正的组件开始的路径一样多。但是，这也意味着您的路径可能过长。

我考虑过可能会尝试以某种方式修改图表，可能是通过复制黑到白边或白到黑边指向的图表，或者复制或删除边，但我没有想到我的头脑 Storm 似乎奏效了。

Answer 1

评论中提到使用 Dijkstra 算法，实际上有一种方法可以做到这一点。如果我们在图中创建一个新的“根”顶点，并使用有向边将所有其他顶点连接到它，我们可以从根向外运行修改后的 Dijkstra 算法，当给定路径的反转超过 n。重要的是要注意，我们必须允许在实现中重新访问每个顶点，因此我们优先级队列中每个顶点的键将不仅仅是 node_id，而是一个元组 (node_id, inversion_count) ，表示第 i 次访问的顶点。这样做时，我们隐式地为每个顶点制作了 n 副本，每次潜在访问一个副本。从视觉上看，我们正在有效地制作我们的图的 n 副本，并转换每个 (black_vertex, white_vertex) 对之间的边以连接 i和第 i+1 个反演图。我们运行该算法，直到我们到达具有 n 个反转的路径。或者，我们可以将第 n 反转图上的每个顶点连接到一个“汇”顶点，并在此图上运行任何传统的寻路算法，不加修改。这将在 O(n(E + Vlog(nV))) 时间内运行。您可以对其进行大量优化，还可以考虑改用 A*，将 smallest_inversion_weight * (n - inversion_count) 作为启发式。

此外，关于使用反转要求的知识来加速搜索，我想到了另一个想法，但我无法在不超过 O(V^2) 时间的情况下找到实现它的方法。这个想法是，您可以使用加法链(如二进制求幂)将最短的 n 反转路径分解为两条较小的路径，然后以分而治之的方式冲洗和重复。问题是您需要为从任意两个顶点的最短 i 反转路径构造表，这将是每个 i 的 O(V^2) 条目 和 O(V^2logn) 整体。要构建每个表，对于上表中的每个条目，您需要附加 V 其他路径，因此总体时间为 O(V^3logn)。也许其他人会看到一种将这两个想法合并为 O((logn)(E + Vlog(Vlogn))) 时间算法或其他东西的方法。