查找路径权重最低的两个顶点 [英] Find Two vertices with lowest path weight

问题描述

我正在尝试解决此问题，但遇到了麻烦。

，需要一些帮助，谢谢。

I am trying to solve this question but got stuck.
Need some help,Thanks.

给出一个无向连通图

设A为V（G）的子组，其中V（G）为G中的顶点组。

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

我想到了在每个节点中使用Dijkstra算法的想法，这会给我O（V *（（E + V）logv））），这实在太多了。

因此，想到以某种方式连接顶点，没有找到任何有用的方法。

还尝试了改变Dijkstra的方法算法有效，但是很难证明，而不会提高时间复杂度。

I got the idea of using Dijkstra's algorithm in each node which will give me O(V*((E+V)logv))),which is too much.
So thought about connecting the vertices in A somehow,did'nt find any useful way.
Also tried changing the way Dijkstra's algorithm work,But it get's to hard to prove with no improvment in time complexity.

推荐答案

请注意，如果最优对是（a，b），然后从最优路径 a u 的每个节点code>和 b 是

Note that if the optimal pair is (a, b), then from every node u in the optimal path, a and b are the closest two nodes in A.

我相信我们应该以以下方式扩展Dijkstra算法：

I believe we should extend Dijkstra's algorithm in the following manners:

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 最小的节点。

1. Start with all nodes in A, instead of a single source_node.
2. For each node, don't just remember the shortest_distance and the previous_node, but also the closest_source_node to remember which node in A gave the shortest distance.
3. Also, for each node, remember the second_shortest_distance, the second_closest_source_node, and previous_for_second_closest_source_node (shorter name suggestions are welcome). Make sure that second_closest_source_node is never the closest_source_node. Also, think carefully about how you update these variables, the optimal path for a node can become part of the second best path for it's neighbour.
4. Visit the entire graph, don't just stop at the first node whose closest_source and second_closest_source are found.
5. Once the entire graph is covered, search for the node whose shortest_distance + second_shortest_distance is smallest.

这篇关于查找路径权重最低的两个顶点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！