找到一条从顶点 s 到顶点 t 的路径，且颜色交替数最少

Find a path from vertex s to vertex t with minimal number of color alternates

设 be a directed graph, and let 为红色和蓝色的 edge-coloring。令 s,t 为 G 中的顶点。找到一条从 s 到 t 的路径（如果存在），使这条路径上的颜色变化次数最少。

我试过如下：

  1. 设为去掉所有 G 的 blue-colored 条边。设 为获得的图 通过删除 G.
    2. 的所有 red-colored
  2. 让 是 strongly connected graph of ，已计算 使用 this 算法。
  3. 让成为 strongly connected graph of ，计算使用 this算法。
  4. 为的顶点着色 为红色，并为 蓝色。
  5. 让成为 通过将 与 .
  6. 定义每个（现有）的权重 G' 中的边为 0.
  7. 对于每个 这样你 属于强连通分量 和 v 属于强连通分量 做为 如下：
  1. 使用Dijkstra算法求最短 从 s 的蓝色强连通分量到 t 的蓝色和红色强连通分量。
  2. 使用 Dijkstra 从红色强连通中寻找最短路径的算法 s 的分量，与蓝色和红色都强连接 t 的组成部分。
  3. 令 p 表示我们四个中的最短路径 刚刚发现。 （即，p 具有最少数量的颜色交替）。 p 是一系列强连通分量。 分别用DFS展开，在G中找到对应的路径。

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

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

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

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

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

最后 t 中的数字是为达到 t.

执行的最少交换次数