如何找到最短的彩色路径？ [英] How to find the shortest colored path?

问题描述

给出G =（V，E），每个边缘都有以下三种颜色之一（绿色，红色，蓝色）。
如果路径中包含所有三种颜色，我们将其称为彩色路径。

Given G=(V,E) Which is every edge has one of these three colors {green,red,blue}. We call a path "Colored Path" if he has all the three colors in it.

    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

我的解决方案是遍历图形，并为每个顶点计数路径具有的颜色数量。创建3个名为G1，G2，G3的图的副本

My solution is to walk through the graph, and count for every vertex the number of colors that the path has. Create 3 copies of the graph named G1,G2,G3

对于每个v（c（v）= 2（c是从s到此路径的颜色数））连接在第二个图形（G2）中从v1到v2，边权重= 0。

For every v that c(v) = 2 (c is number of colors from s to this path) connect v1 to v2 in the second graph(G2) with edge weight = 0.

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

for every edge c(v)= 3 connect from v2 (From G2) to v3 (To G3) with edge weight = 0 .

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

run dijkstra from s to t3 (in G3).

我的解决方案对吗？

推荐答案

在我看来不正确。

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

The easiest way is to realize that in normal Dijkstra, there's only one important thing to store in each node, and that's the absolute shortest path length from the root.

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

With colored paths, you have to store the shortest path length for every color combination. So, for 3 colors, you have to store the shortest red path, the shortest blue path, the shortest green path, as well as the shortest red-blue, red-green and blue-green paths, and finally the shortest red-green-blue path. (Total of 7 color combinations).

这篇关于如何找到最短的彩色路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！