在给定多个图的情况下找到两个节点之间的最短距离。

Question

3

假设我们有一组节点和多个不同边缘的图。我需要找到两个节点之间的最短路径。例如，有三个图形，如图所示，分别为graph 01, graph 02和graph 03。我需要找到node 1和node 7之间的最短路径。

由于一个图中没有路径，我已经使用了多个图。因此结果应该如下所示。

尽管下面显示的路径使用的边比上面的图少，但由于图形之间的转换更多，应将上述路径视为最短路径。

在这里，路径最短的最重要术语是从图形到图形的转换次数。我该如何解决这个问题？

- PrabodhanaJ

3

看起来您可以将它建模为一个带有加权边的新图。每个节点被拆分为原始图中的各个节点，并且原来的边转化为它们之间权重为1的边。然后在所有对应节点之间添加边，但是给它们赋予非常高的权重（例如大于新图中边的总数），或者在成本分析中特别处理它们。 - tehtmi

2个回答

0

创建一个新的图，其中：

最后，在考虑多源的情况下运行BFS 0/1算法，源点分别为(0, source), (1, source)和(2, source)，在新图中考虑以下可能的目标点：(0, target), (1, target)和(2, target)。得到答案需要考虑这些目标点。

复杂度为O(V + E)。

请查看我的代码以获取更多细节：ideone.com/iDlm38

- Marco Cáceres

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- גלעד ברקן · Accepted Answer

这种情况下，这些图表可能会有点误导性。如果“最短路径”的距离度量是路线上图形转换的次数，那么对于每个单独的图形，我们在任何一对连接节点之间（可以互相到达的节点）之间有权重为0的边缘。

然后，在不同图形之间共享的节点对之间，我们有权重为1的边缘。