algorithm - 给定多个图找到两个节点之间的最短距离

Question

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

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

尽管与上图相比，下图路径使用的边数较少，但由于图之间的转换较高，因此应将上述路径视为最短路径。

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

标签： algorithmgraph-theoryshortest-path

Answer 1

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

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