1

设$G=(V,E)$为有向图，设$c:E\mapsto {红、蓝}$为红色和蓝色的边缘着色。让 s,t 是 G 中的顶点。找到一条从 s 到 t 的路径（如果存在），使得沿着这条路径的颜色变化次数最少。

我试图做如下：

  1. 让$G_r$是通过去除 G 的所有蓝色边缘$G_b$得到的图。让 是通过去除 G 的所有红色边缘得到的图。
  2. 让$G_{r}^{SCC}$ 是 的强连通图$G_r$，使用该算法计算。
  3. 让$G_{b}^{SCC}$是 的 强连通图$G_b$，使用 该算法计算。
  4. 将 的顶点 $G_{r}^{SCC}$着色为红色，将 的顶点着色为 $G_{b}^{SCC}$蓝色。
  5. 设为与 $G'=(V',E')$合并得到的图。$G_{r}^{SCC}$$G_{b}^{SCC}$
  6. 将 G' 中每个（现有）边的权重定义为 0。
  7. 对于每个$(u,v)\in E$这样的 u 属于强连通分量$C_u$，v 属于强连通分量$C_v$，请执行以下操作：
  • 如果$C_u \neq C_v$并将$color(C_u)\neq 颜色(C_v)$边缘添加$(C_u ,C_v)$到 G' 并将其权重定义为 1。
  1. 使用 Dijkstra 算法找到从 s 的蓝色强连通分量到 t 的蓝色和红色强连通分量的最短路径。
  2. 使用 Dijkstra 算法找到从 s 的红色强连通分量到 t 的蓝色和红色强连通分量的最短路径。
  3. 让 p 表示我们刚刚找到的四个路径中的最短路径。（即，p 具有最少数量的颜色替代）。p 是一系列强连通分量。使用 DFS 展开它们中的每一个，以在 G 中找到相应的路径。

该算法可以在 O(E+V*log(v)) 中运行。可以改进或简化吗？

4

1 回答 1

1

我不完全理解你的算法，特别是在第 4 阶段，你将用两种不同颜色的边缘为每个顶点着色 - 蓝色和红色......
因此，我不会尝试改进你的算法，但会展示我自己的一个 - BFS 的变体，时间为 O(E + V)。

想法：遍历图形的边缘并测量深度作为您切换颜色的次数。

注意：我们将运行算法两次，首先假设路径的第一条边是红色的，第二次假设路径的第一条边是蓝色的，然后取最小值。

  1. 仅在从 s 开始的红色边上运行 BFS（这是 BFS 队列中的第一个元素），如果您在蓝色边上查看顶点，请将其保留在不同的队列中。
  2. 用数字标记您看到的所有节点i（在开头i=0）。
  3. 将蓝色边缘的队列设为您的主要队列。
  4. 运行阶段 1 到 3，但切换颜色并将 1 添加到i.

最后， int的数字是为达到 所执行的最小交换次数t。

于 2020-07-14T21:58:33.577 回答