找出所有可能的方法来连接一个断开连接的无向图，并为每种可能性计算从src到目的地的最短路径

Question

在这个问题中，你会得到一个断开连接的无向图和每个顶点之间的距离的2D矩阵。我试图找到所有可能的方法来从这个状态制作一个连接的图，然后计算每个可能的组合从顶点0到顶点1的最短路径的距离。顶点0被选择为源顶点，所有具有到顶点0路径的顶点都被认为是连接的，所有没有到顶点0路径的顶点都没有连接。我试图使用BFS找到所有可能的路径，但使用动态规划进行优化，但无法弄清楚子问题和数据结构应该是什么。

例如，给定此图，其中V={0,1,2}和adj矩阵（第一个）以及每个矩阵之间的距离（第二个）：

  0 1 2          0 1 2
0 0 0 0        0 0 3 4
1 0 0 1        1 3 0 1
2 0 1 0        2 4 1 0

由于顶点1和2没有连接，如果我连接0到1，最短路径的长度将是3。如果我连接0到2，从0到1的最短路径将是4 1。两种情况的可能性相同。

子问题是什么？我应该如何解决这个问题？

Answer 1

将连接的组件折叠为多重图（多条边可以连接两个顶点的图）的单个顶点。使用任何回溯搜索来枚举多重图的所有生成树。

这个任务的不可约复杂度是K！，其中K是连通分支的数量。

用传递闭包算法计算连通分支。