如何找到最短的彩色路径？

给定G =（V，E）每条边都有这三种颜色{绿，红，蓝}中的一种。如果他拥有所有三种颜色，我们称之为“彩色路径”。如何找到最短的彩色路径？

Input: graph G(V,E),weight function w:E->Q+ , colored edges and vertices s . 
    output: algorithm that finds for every vertices v, a shortest path from s 
      that is Colored path

我的解决方案是通过图形行走，计数每个顶点的路径具有颜色数。创建名为G1，G2的图形的3个拷贝，G3

对于每一个信息v C（V）= 2（c是从s的颜色编号，以该路径）连接V1的第二曲线（G2）到V2与边缘权重= 0。

对于每个边缘c（v）= 3从边缘权重= 0的v2（从G2）到v3（到G3）连接。

将dijkstra从s运行到t3（在G3中）。

我的解决方案是否正确？

来源

2017-01-30 elias rizik

与'古典'全对最短路径问题不同的是，可能存在顶点“u”，“v”，其中根本没有从u到v的彩色路径，即使图已连接;由于边的类别，问题似乎也不容易分解，因为彩色路径可以分解为不是彩色路径的路径。 – Codor

你能举一个更详细的建筑例子吗？ – Codor

你的算法的描述是没有意义的。什么是“每边c（v）= 3”？什么是“从s到这个路径的颜色数量”？ – user31264

对我来说看起来不正确。

最简单的方法是认识到，在正常的Dijkstra中，每个节点只存储一件重要的事情，那就是从根开始的绝对最短路径长度。

使用彩色路径，您必须存储每个颜色组合的最短路径长度。因此，对于3种颜色，您必须存储最短的红色路径，最短的蓝色路径，最短的绿色路径，以及最短的红蓝绿色路径，最后是最短的红绿色路径 - 蓝色路径。（共有7种颜色组合）。

来源

2017-01-30 13:28:52 MSalters

似乎是正确的，解释是非常有见地的。不知何故，我期待这个问题在复杂性方面更难。为了更加简洁：Dijkstra的算法适用于单一来源版本，而不是全部版本。 – Codor

@Codor：公平点; Dijkstra对于所有路径都是低效的。 – MSalters

如何找到最短的彩色路径？

回答

相关问题