彩色边图中的最短路径

在无向和连通图中，每条边都有一个颜色（红色，绿色或蓝色）。
一个有效的路径是一个至少有一个边的每个颜色的路径。
问题是如何找到最短的有效路径或确定不存在。彩色边图中的最短路径

我试图使用BFS，但无法找出解决方案。
关于如何开始的任何想法？

来源

2011-03-20 ThP

我会使用BFS，并从每个节点开始，计算可从该节点发现的第一个有效路径，保存该值并转到下一个节点。

该图可以用矩阵表示，每个边的颜色（比如-1（无边），0,1,2）表示为矩阵中边的值。

当你发现它们时，路径可以放入一对数组中，一个保存路径中的步骤和一个检查三种颜色的数组。

来源

2011-03-20 19:59:47 philosodad

在最坏的情况下不需要很长的运行时间吗？ – ThP 2011-03-20 21:26:20

那么，一般来说所有的最短路径都是n^3，所以你的解决方案可能会有相当高的运行时间。一旦你有了一个可行的解决方案，你应该能够弄清楚如何节省运行时间。 – philosodad 2011-03-21 12:55:03

首先，我假设颜色的数量是固定的。那我就提出了一个标签设置Dijkstra算法（帕累托Dijkstra算法比较）导致的O运行时间（N日志（N）+ M）：

使用广义的Dijkstra算法寻找最短路径：每个节点有一个标签列表，一个标签由起始节点的长度和所有尚未访问的颜色组成。（1）它的长度小于和（2）它包含了另一个标签的所有颜色。一个主导的标签被直接删除。与dijkstra相似，您需要保留一个优先级队列，您可以从中轻松放松长度较短的节点。采用边缘到节点v将增加标签的长度，并将边缘的颜色添加到标签。将标签添加到节点v的标签列表中当使用包含所有三种颜色的标签建立目标节点时，您找到了最短路径。请注意，如果要在最后重建最短路径，则必须为每个标签保存前驱节点。

您以起始节点（0，{}）（零长度且无颜色）的起始标签开始。

每个节点可被每个颜色集组合至多一次结算，因为仅存在8（固定），例如在这种情况下的组合，运行时间等于Dijkstra算法，其为O（n *的log（n） + m）以获得最佳实施。

来源

2011-03-29 10:48:15 eci

该方法没有描述当到达目的地时会发生什么，但没有获得足够的颜色。需要反弹的方法来补充解决方案。 – Wei 2011-04-19 13:46:52

最后，你会（如果可能的话）有几个标签到达目的地。当包含所有颜色（红色，绿色，蓝色）的第一个标签在目的地处结算时，您停止运算法则，但不会更早。如果算法在没有找到这样的标签的情况下停止，那么使用所有三种颜色从s到t是不可能的。 – eci 2011-04-26 11:14:48

-1

创建一个新图形（6次）包含原始图像的三个副本，第一个仅包含其中一种颜色的边，第二个包含另一种颜色的边，并将它们与边连接从第二种颜色开始，第三个副本将具有所有的边，并且与第三种颜色的边连接到第二个图。然后运行dijkstra找到从s1到t3的最短路径。因为我们不知道什么样的顺序，我们会为颜色的全部6个可能的顺序做同样的事情，然后选择我们得到的6条最短路径中最短的一条。

来源

2012-01-25 19:29:00

我不认为这是正确的算法。如果我理解正确，这只允许改变颜色两次的路径。但是，根据问题，如果路径至少**两次更改颜色**，路径才是有效的。 – blubb 2012-01-25 20:31:41

确实存在如下简单的解决方案。

假设没有颜色，在图上做一个正常的dijkstra。

猜猜3个边缘每种颜色之一。对于所有的m^3可能的猜测，让边为r1 --- r2，b1 --- b2，g1 --- g2，我们得到24种可能的方式，他们可以进入路径（8为你可以定位边的方式，6为排列）。

既然你已经有了正常的dijkstra数据，一旦你完成了这个工作，你可以在不断的时间得到结果，最大限度地减少所有的猜测。

对所有n个顶点重复此操作。

我的确同意最终的复杂度O（nm^3）通常太大，但有时候这个微不足道的算法是有效的。

来源

2012-01-29 22:01:48 Manyu

彩色边图中的最短路径

回答

相关问题