具有最短路径的两个顶点
Two vertices with shortest path
我正在尝试解决这个问题，但卡住了。
需要一些帮助，谢谢。
给定一个边上有非负值的无向连通图 G。
设A是V(G)的子群，其中V(G)是G中的顶点群。
-找到属于A的一对顶点(a,b)，使得它们之间的最短路径在G中的权重最小，在O(V*(E+Vlog (v)))
我想到了在每个节点中使用 Dijkstra 算法，这将给我 O(V*(E+Vlog(v)))。我认为这太多了，我们可以通过使用 Dijkstra 一次来完成。
于是想了想把A中的顶点连接起来，没找到什么有用的方法
让我们通过一个例子来理解上面的场景。
让图表 G 包含 - a, b, c, d, e, f 即
V(G) = {a,b,c,d,e,f}
现在如前所述，A 是 V(G) 的一个子群，所以我们假设
A = {a,b,c}
现在 运行 Floyd–Warshall algorithm 遍历此图，这基本上将为您提供所有顶点对之间的最短路径。
并且该算法的总体时间复杂度为 O(V^3)，其中 V 是图中的顶点数。
完成此算法后，您可以轻松检查子组 A 中存在哪两对顶点。
希望对您有所帮助！
我正在尝试解决这个问题，但卡住了。 需要一些帮助，谢谢。
给定一个边上有非负值的无向连通图 G。
设A是V(G)的子群，其中V(G)是G中的顶点群。
-找到属于A的一对顶点(a,b)，使得它们之间的最短路径在G中的权重最小，在O(V*(E+Vlog (v)))
我想到了在每个节点中使用 Dijkstra 算法，这将给我 O(V*(E+Vlog(v)))。我认为这太多了，我们可以通过使用 Dijkstra 一次来完成。 于是想了想把A中的顶点连接起来，没找到什么有用的方法
让我们通过一个例子来理解上面的场景。
让图表 G 包含 - a, b, c, d, e, f 即
V(G) = {a,b,c,d,e,f}
现在如前所述，A 是 V(G) 的一个子群，所以我们假设
A = {a,b,c}
现在 运行 Floyd–Warshall algorithm 遍历此图，这基本上将为您提供所有顶点对之间的最短路径。
并且该算法的总体时间复杂度为 O(V^3)，其中 V 是图中的顶点数。
完成此算法后，您可以轻松检查子组 A 中存在哪两对顶点。
希望对您有所帮助！