找到路径权重最低的两个顶点

Question

我正在尝试解决这个问题，但卡住了。
需要一些帮助，谢谢。

给定一个边上有非负值的无向连通图 G。
设A是V(G)的子群，其中V(G)是G中的顶点群。

-找到属于A的一对顶点(a,b)，使得它们之间的最短路径在G中的权重最小，在O((E+V)*日志(v)))

我想到在每个节点中使用 Dijkstra 算法，这会给我 O(V*((E+V)logv)))，这太多了。
于是想了想把A中的顶点连接起来，没找到什么有用的方法
还尝试改变 Dijkstra 算法的工作方式，但在时间复杂度没有改进的情况下很难证明。

Answer 1

注意，如果最优对是(a, b)，那么从最优路径中的每个节点u，a和b是[中最近的两个节点=14=].

我认为我们应该按以下方式扩展 Dijkstra 算法：

1. 从 A 中的所有节点开始，而不是单个 source_node.
2. 对于每个节点，不要只记住shortest_distance和previous_node，还要记住closest_source_node，记住A中哪个节点给出的距离最短.
3. 此外，对于每个节点，请记住 second_shortest_distance、second_closest_source_node 和 previous_for_second_closest_source_node（欢迎建议更短的名称）。确保 second_closest_source_node 永远不是 closest_source_node。另外，请仔细考虑如何更新这些变量，节点的最佳路径可以成为其邻居的第二最佳路径的一部分。
4. 访问整个图，不要只停留在找到 closest_source 和 second_closest_source 的第一个节点。
5. 覆盖整个图后，搜索 shortest_distance + second_shortest_distance 最小的节点。