带有所需顶点的有向加权图 [英] Directed Weighted Graph with required vertices

问题描述

给出:一个有向加权图G =(V，E)，一些顶点是红色，一些蓝色，其余白色，权重Ti是从任何一个顶点红色顶点到任何一个顶点所允许的最大权重蓝色顶点.

Given: A directed, weighted graph G=(V, E), some of the vertices are red, some blue, and the rest white, weight Ti which is the maximum weight allowed to go from any vertex red vertex to any blue vertex.

问题:创建一种算法，以最小的权重找到从源节点S到目标节点T的路径，并且该路径在到达顶点T之前从红色顶点到蓝色顶点的最大权重为Ti.该算法.应该具有时间复杂度O(n ^ 3)

Problem: Create an algorithm that finds a path from source node S, to target node T with least weight and which at some point goes from a red vertex to a blue vertex in at most Ti weight before reaching vertex T. The algorithm should have time complexity O(n^3)

评论:我不确定该如何开始，我认为这是Dijkstra算法的某种变体，而且我看到有些人在谈论制作图形的副本并连接这些副本，但除此之外，不确定此算法的设置是什么样.任何帮助将不胜感激.

Comments: I'm not sure how to get started on this, I figure it's some variation of Dijkstra's algorithm and I've seen some people talking about making copies of the graphs and connecting the copies but beyond that, I'm not sure what the setup of this algorithm would look like. Any help would be appreciated.

推荐答案

实际上，您可以使用以下复制策略:

Indeed, you can use the copy-strategy as follows:

将图形 G 复制到 G'和 G" .与 G 中一​​样，将 G'中的所有顶点标记为，但要加上撇号.因此，在 G'中有一个 S'和一个 T'.同样， S" 和 T" 属于 G" .

Copy the graph G to G' and to G". Label all vertices in G' as in G, but with the apostrophe. So there is an S' and a T' in G'. Similarly, S" and T" belong to G".

让 S 为起始顶点，以 T" 为目标.就目前而言， G ， G'和 G" 已断开连接.但是添加以下零重量定向边:

Let S be the start vertex, and T" be the target. As it stands now, G, G' and G" are disconnected. But add the following zero-weight, directed edges:

• 从 G 中每个红色顶点 r 到其 G'中其镜像 r'的边./li>
• 从 G'中每个蓝色顶点 b'到其 G'中其镜像 b'''的边

• Edges from each red vertex r in G, to its mirror r' in G'.
• Edges from each blue vertex b' in G', to its mirror b" in G".

因此，没有从 G'到 G'的路径，也没有从 G'到 G 的路径，也不是 G" 到 G .

So there are no paths from G" to G', nor from G' to G, nor from G" to G.

现在在 S 中启动Dijkstra算法，为优先级队列中的每个条目添加一个额外的数据属性: G'中边缘所累积的路径的权重仅.我们称其为 w'.此 w'在队列的优先级中不起作用.路径的 total 权重决定了优先级，这是Dijkstra算法中的标准.该算法不应扩展 w'超过 Ti 的路径.除了该特定限制外，该算法的其余所有部分都可以像标准Dijkstra算法一样保留.

Now start a Dijkstra algorithm in S, with an additional data attribute for each entry in the priority queue: the weight that a path accumulated by edges in G' only. Let's call this w'. This w' plays no role in the priority of the queue. The total weight of a path determines the priority as is standard in Dijkstra's algorithm. The algorithm should not expand paths whereby w' would exceed Ti. Besides that specific limitation, all the rest of the algorithm can remain as in the standard Dijkstra algorithm.

这篇关于带有所需顶点的有向加权图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！