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

Question

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

给定无向连通图G，边缘处具有非负值。 设A是V（G）的子群，其中V（G）是G中的顶点群。

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

我想到在每个节点中使用Dijkstra算法，这将给我O（V *（（E + V）logv））），这太多了。 所以考虑以某种方式连接A中的顶点，没有找到任何有用的方法。 还尝试改变Dijkstra算法的工作方式，但是在时间复杂度上没有改进的情况下很难证明。

Answer 1

注意，如果最佳对是(a, b)，那么从最优路径中的每个节点u，a和b是A中最接近的两个节点。

我相信我们应该以下列方式扩展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最小的节点。