我有一个带有彩色加权边的有向图 . 有2种颜色 . 每个边缘只能有1种颜色 . 我想找到颜色变化有限的最短路径 . 从一个顶点可以出现最多2个边缘，其中有2种不同的颜色，2个边缘有2种不同的颜色 .
例如，在此图中：
最短路径最多3个颜色变化 9 最大 0 颜色变化最短路径是 6+1+4=11 等 .
9
0
6+1+4=11
我的解决方案是递归访问所有可能的路径并交换，如果递归找到一个更好的，使这个问题呈指数级 .
是否存在针对此问题的非指数解决方案？
这可以通过在适当构造的图上运行Dijkstra算法在时间O（nm n2 log n）中求解 .
为了激发我们前进的直觉，让我们假设最佳路径最多只能产生一种颜色变化，并从红色边缘开始 . 因此，路径不遵循蓝色边缘，在这种情况下，我们只跟随红色边缘，或者它遵循一定数量的红色边缘，然后是一些蓝色边缘 .
想想如果你按如下方式变换G会发生什么：
首先将图形中的节点复制两次，得到两层G0和G1 . 我们将G0中的节点v的副本表示为v0，将G1中的节点v的副本表示为v1 .
对于每个蓝色边缘（u0，v0），用边（u0，v1）替换该边 .
删除G1中的所有红色边缘 .
您可以将此图表视为G的两个副本堆叠在一起，并对边缘进行一些调整 . 具体来说，在G0内部运行的边缘都是红色，蓝色边缘将您带到G1 . G1中没有红色边缘 .
想想这个图表中的路径是什么样的 . 如果你纯粹保持在G0，它只包含红色边缘 . 如果从G0开始并以G1结束，那么路径开始是通过跟随一些红色边缘，然后是至少一个蓝色边缘，然后是一些更大数量的蓝色边缘 . 因此，此图中的任何路径都只包含一个颜色变化 .
您可以使用此图来查找从节点u到节点v的最短路径，该路径最多只能进行一次颜色更改 . 首先运行从u开始的Dijkstra算法，然后查看v0和v1的距离 . 到v0的距离是到v0的最短路径的长度，没有颜色变化 . 到v1的距离是到v1的最短路径的长度，最多可以产生一次颜色变化 . 这两个距离中较短的距离为您提供从u到v的最短路径的长度，最多可以产生一种颜色变化 .
我们可以扩展这个技巧以适用于任何数量的步骤k，如下所示 . 创建G的k个副本，称为G0，G1，G2，...，G（k-1） . 假设路径以红色边缘开始，我们可以按如下方式更改图形 . 使G0中的所有蓝色边缘从G0运行到G1 . 然后，使G1中的所有红色边缘从G1运行到G2 . 然后，使G2中的所有蓝色边缘从G2运行到G3等 . 最后，删除G（k-1）中不是通向G（k-1）的颜色的所有边缘 . 该图保持与以前相同的属性 - 从节点u0到节点v_r的任何路径表示从u到v的路径，其精确地进行r颜色变化，假设第一个边是红色 . 然后，通过查看到v_0，v_1，...，v_（k-1）的路径的最低成本，可以找到最多产生r颜色变化的最佳路径 .
到目前为止，这种方法假设第一步是红色，但我们不能保证是这种情况 . 但是没关系 - 我们可以运行这个算法，假设第一步是红色，一旦假设第一步是蓝色，并采取两个选项的最佳 .
那么这有多贵？好吧，如果我们得到最多k个颜色变化，我们构造的图形将具有总共O（nk）个节点和O（mk）个边缘，因此构造它将花费时间O（k（m n）） . 在图中运行Dijkstra以找到到所有目标节点的最短路径然后花费时间O（mk nk log nk），因此总运行时间为O（mk nk log nk） .
我们实际上可以在O（mn n2 log n）处将其上限，原因如下：由于所有边都具有严格的正权重，因此我们知道没有路径可以产生超过n - 1个颜色的变化 . 如果一个路径，它将至少有n个边，所以它将有一个循环 . 这个周期具有严格的正成本，因此我们可以通过消除周期来提高成本 . 因此，如果k≥n，我们可以将k上限设为n . 将k = n插入上述表达式得到O（mn n2 log n）的渐近运行时 .
希望这可以帮助！
一种解决方案是运行Dijkstra的算法，但使用两级堆 .
两个主要结构如下 .
一个hashmap / dictionary，它将颜色更改的数量映射到包含具有确切颜色更改数量的所有活动路径的最小堆 .
k-way合并堆，它接收在＃1中映射到的堆，当前最小距离并产生具有最小距离的堆 .
主要功能的psudeocode如下：
ExtractMin（）：从k-way堆中提取min . 这导致了min所属的＃颜色变化堆 . 新的min从颜色更改堆中提取，然后添加回k-way堆（映射到它的颜色更改堆） .
add（路径，长度，颜色更改次数）：使用该数量的颜色更改查找堆并将路径插入其中，如果堆尚不存在则创建堆 . 如果那是该堆的新min，则通过reduce键在k-way合并堆中更改该数量的颜色更改堆的min，并将唯一值替换为新值 .
换句话说，使用每个颜色变化数量的堆，并将每个堆的最小值插入另一个最小堆中，用于查找实际最小值 .
为了防止它与标准的Dijkstra算法等效，您只需添加具有太多颜色更改的路径到两级堆 . 你可以使用类似的东西：
if number_color_changes <= max_color_changes: data_structure.add(path, length, number_color_changes)
这也可用于查找每个颜色变化数小于或等于最小颜色变化数的最小路径 .
至于处理颜色变化本身 . 每个路径与计数器相关联，并且在Dijkstra的扩展步骤期间，进行检查以确定边缘颜色是否改变并且新路径的计数器是否被更新以反映该路径 .
渐近性能应该与使用相同类型的堆的Dijkstra算法大致相同 .
2 回答
这可以通过在适当构造的图上运行Dijkstra算法在时间O（nm n2 log n）中求解 .
为了激发我们前进的直觉，让我们假设最佳路径最多只能产生一种颜色变化，并从红色边缘开始 . 因此，路径不遵循蓝色边缘，在这种情况下，我们只跟随红色边缘，或者它遵循一定数量的红色边缘，然后是一些蓝色边缘 .
想想如果你按如下方式变换G会发生什么：
首先将图形中的节点复制两次，得到两层G0和G1 . 我们将G0中的节点v的副本表示为v0，将G1中的节点v的副本表示为v1 .
对于每个蓝色边缘（u0，v0），用边（u0，v1）替换该边 .
删除G1中的所有红色边缘 .
您可以将此图表视为G的两个副本堆叠在一起，并对边缘进行一些调整 . 具体来说，在G0内部运行的边缘都是红色，蓝色边缘将您带到G1 . G1中没有红色边缘 .
想想这个图表中的路径是什么样的 . 如果你纯粹保持在G0，它只包含红色边缘 . 如果从G0开始并以G1结束，那么路径开始是通过跟随一些红色边缘，然后是至少一个蓝色边缘，然后是一些更大数量的蓝色边缘 . 因此，此图中的任何路径都只包含一个颜色变化 .
您可以使用此图来查找从节点u到节点v的最短路径，该路径最多只能进行一次颜色更改 . 首先运行从u开始的Dijkstra算法，然后查看v0和v1的距离 . 到v0的距离是到v0的最短路径的长度，没有颜色变化 . 到v1的距离是到v1的最短路径的长度，最多可以产生一次颜色变化 . 这两个距离中较短的距离为您提供从u到v的最短路径的长度，最多可以产生一种颜色变化 .
我们可以扩展这个技巧以适用于任何数量的步骤k，如下所示 . 创建G的k个副本，称为G0，G1，G2，...，G（k-1） . 假设路径以红色边缘开始，我们可以按如下方式更改图形 . 使G0中的所有蓝色边缘从G0运行到G1 . 然后，使G1中的所有红色边缘从G1运行到G2 . 然后，使G2中的所有蓝色边缘从G2运行到G3等 . 最后，删除G（k-1）中不是通向G（k-1）的颜色的所有边缘 . 该图保持与以前相同的属性 - 从节点u0到节点v_r的任何路径表示从u到v的路径，其精确地进行r颜色变化，假设第一个边是红色 . 然后，通过查看到v_0，v_1，...，v_（k-1）的路径的最低成本，可以找到最多产生r颜色变化的最佳路径 .
到目前为止，这种方法假设第一步是红色，但我们不能保证是这种情况 . 但是没关系 - 我们可以运行这个算法，假设第一步是红色，一旦假设第一步是蓝色，并采取两个选项的最佳 .
那么这有多贵？好吧，如果我们得到最多k个颜色变化，我们构造的图形将具有总共O（nk）个节点和O（mk）个边缘，因此构造它将花费时间O（k（m n）） . 在图中运行Dijkstra以找到到所有目标节点的最短路径然后花费时间O（mk nk log nk），因此总运行时间为O（mk nk log nk） .
我们实际上可以在O（mn n2 log n）处将其上限，原因如下：由于所有边都具有严格的正权重，因此我们知道没有路径可以产生超过n - 1个颜色的变化 . 如果一个路径，它将至少有n个边，所以它将有一个循环 . 这个周期具有严格的正成本，因此我们可以通过消除周期来提高成本 . 因此，如果k≥n，我们可以将k上限设为n . 将k = n插入上述表达式得到O（mn n2 log n）的渐近运行时 .
希望这可以帮助！
一种解决方案是运行Dijkstra的算法，但使用两级堆 .
两个主要结构如下 .
一个hashmap / dictionary，它将颜色更改的数量映射到包含具有确切颜色更改数量的所有活动路径的最小堆 .
k-way合并堆，它接收在＃1中映射到的堆，当前最小距离并产生具有最小距离的堆 .
主要功能的psudeocode如下：
ExtractMin（）：从k-way堆中提取min . 这导致了min所属的＃颜色变化堆 . 新的min从颜色更改堆中提取，然后添加回k-way堆（映射到它的颜色更改堆） .
add（路径，长度，颜色更改次数）：使用该数量的颜色更改查找堆并将路径插入其中，如果堆尚不存在则创建堆 . 如果那是该堆的新min，则通过reduce键在k-way合并堆中更改该数量的颜色更改堆的min，并将唯一值替换为新值 .
换句话说，使用每个颜色变化数量的堆，并将每个堆的最小值插入另一个最小堆中，用于查找实际最小值 .
为了防止它与标准的Dijkstra算法等效，您只需添加具有太多颜色更改的路径到两级堆 . 你可以使用类似的东西：
这也可用于查找每个颜色变化数小于或等于最小颜色变化数的最小路径 .
至于处理颜色变化本身 . 每个路径与计数器相关联，并且在Dijkstra的扩展步骤期间，进行检查以确定边缘颜色是否改变并且新路径的计数器是否被更新以反映该路径 .
渐近性能应该与使用相同类型的堆的Dijkstra算法大致相同 .