在无向和连通图中，每条边都有一种颜色（红色，绿色或蓝色） .有效路径是具有每种颜色的至少一个边缘的路径 .问题是如何找到最短的有效路径或确定不存在 .
我试图使用BFS但无法找出解决方案 .关于如何开始的任何想法？
我会使用BFS，并从每个节点开始，我将计算从该节点可发现的第一个有效路径，保存该值，然后继续下一个 .
图形可以用矩阵表示，每条边的颜色（比如-1（无边），0,1,2）作为矩阵中边的值 .
当您发现它们时，路径可以放入一对阵列中，一个用于保持路径中的步骤，另一个用于检查三种颜色 .
首先，我假设颜色的数量是固定的 . 然后我会提出一个标签设置Dijkstra算法（与Pareto Dijkstra比较），导致运行时间为O（n log（n）m）：
使用广义Dijkstra找到最短路径：每个节点都有一个标签列表，一个标签由起始节点的长度和访问过的所有颜色组成 . 如果（1）它具有较小的长度并且（2）它包括另一个标签的所有颜色，则一个标签在该节点中支配另一个标签 . 直接删除主导标签 . 与dijkstra类似，你保留了一个优先级队列，你可以从中放松长度较短的节点 . 将边缘移到节点v将使标签长度增加到边长，并将边缘的颜色添加到标签 . 标签将添加到节点v的标签列表中 . 当使用包含所有三种颜色的标签 Build 目标节点时，您已找到最短路径 . 请注意，如果要在末尾重建最短路径，则必须为每个标签保存前导节点 .
您从起始节点的初始标签开始，使用（0，{}）（零长度，无颜色） .
每个颜色集组合最多可以安置一个节点，因为在这种情况下只存在8个（固定的）这样的组合，运行时间等于Dijkstra算法，其中O（n * log（n）m）为最佳实现 .
确实存在如下的微不足道的解决方案 .
假设没有颜色，在图表上做一个正常的dijkstra .
猜猜每种颜色中有3个边缘 . 对于所有m ^ 3可能的猜测让边缘为r1 --- r2，b1 --- b2，g1 --- g2我们得到24种可能的方式它们可以进入路径（8种方式可以定位边缘，6为排列） .
由于您已经拥有了正常的dijkstra数据，因此一旦完成此操作，您将获得恒定的结果，最小化所有猜测 .
对所有n个顶点重复此操作 .
我同意最终的复杂度O（nm ^ 3）通常太大，但有时候这个简单的算法也可以工作 .
创建一个新图形（6次）由原始图形的三个副本组成，第一个仅包含其中一种颜色的边缘，第二种颜色包括另一种颜色的边缘，并将它们与第二种颜色的边缘连接起来，第三个副本将具有所有边缘，并连接到第二个图形，边缘来自第三个颜色 . 然后运行dijkstra找到从s1到t3的最短路径 . 因为我们不知道这个顺序是什么，我们将对整个6种颜色的可能顺序做同样的事情，然后选择我们得到的最短6条最短路径 .
4 回答
我会使用BFS，并从每个节点开始，我将计算从该节点可发现的第一个有效路径，保存该值，然后继续下一个 .
图形可以用矩阵表示，每条边的颜色（比如-1（无边），0,1,2）作为矩阵中边的值 .
当您发现它们时，路径可以放入一对阵列中，一个用于保持路径中的步骤，另一个用于检查三种颜色 .
首先，我假设颜色的数量是固定的 . 然后我会提出一个标签设置Dijkstra算法（与Pareto Dijkstra比较），导致运行时间为O（n log（n）m）：
使用广义Dijkstra找到最短路径：每个节点都有一个标签列表，一个标签由起始节点的长度和访问过的所有颜色组成 . 如果（1）它具有较小的长度并且（2）它包括另一个标签的所有颜色，则一个标签在该节点中支配另一个标签 . 直接删除主导标签 . 与dijkstra类似，你保留了一个优先级队列，你可以从中放松长度较短的节点 . 将边缘移到节点v将使标签长度增加到边长，并将边缘的颜色添加到标签 . 标签将添加到节点v的标签列表中 . 当使用包含所有三种颜色的标签 Build 目标节点时，您已找到最短路径 . 请注意，如果要在末尾重建最短路径，则必须为每个标签保存前导节点 .
您从起始节点的初始标签开始，使用（0，{}）（零长度，无颜色） .
每个颜色集组合最多可以安置一个节点，因为在这种情况下只存在8个（固定的）这样的组合，运行时间等于Dijkstra算法，其中O（n * log（n）m）为最佳实现 .
确实存在如下的微不足道的解决方案 .
假设没有颜色，在图表上做一个正常的dijkstra .
猜猜每种颜色中有3个边缘 . 对于所有m ^ 3可能的猜测让边缘为r1 --- r2，b1 --- b2，g1 --- g2我们得到24种可能的方式它们可以进入路径（8种方式可以定位边缘，6为排列） .
由于您已经拥有了正常的dijkstra数据，因此一旦完成此操作，您将获得恒定的结果，最小化所有猜测 .
对所有n个顶点重复此操作 .
我同意最终的复杂度O（nm ^ 3）通常太大，但有时候这个简单的算法也可以工作 .
创建一个新图形（6次）由原始图形的三个副本组成，第一个仅包含其中一种颜色的边缘，第二种颜色包括另一种颜色的边缘，并将它们与第二种颜色的边缘连接起来，第三个副本将具有所有边缘，并连接到第二个图形，边缘来自第三个颜色 . 然后运行dijkstra找到从s1到t3的最短路径 . 因为我们不知道这个顺序是什么，我们将对整个6种颜色的可能顺序做同样的事情，然后选择我们得到的最短6条最短路径 .