0

这个问题是我之前提出的类似问题的延续：Find path between two nodes in graph, based on given criteria - optimization task。

问题摘要：我需要在图中找到从顶点 A 到顶点 B 的最佳路径，假设路径质量计算为路径上边缘权重的最小值，下一个最佳路径是具有最大最小值的路径。通常它就是所谓的“最宽路径问题”。

以前我需要在非常小的图形（最多 15 个顶点）中解决这个问题，所以我不需要复杂的算法，在好心人的帮助下，我设计了我的工作算法。不幸的是，现在我需要以这种方式重新定义我的必需品，以使我的图可以非常大（甚至 5 万条边）。我知道我需要为我的图找到最大生成树，并在获得的 MST 中获得从开始到停止顶点的简单路径。我决定使用jGraphT库。它实现了Kruskal 最小生成树算法。我可以通过将每个边权重乘以 (-1) 并将 Kruskal 用于最小生成树来获得最大生成树，但库中的算法已设计用于检索 MST 边的哈希集。

我的问题如下： 我已经获得了图的最大生成树作为边的 java HashSet。如何以最有效的方式在这种结构中找到从顶点 A 到顶点 B 的路径，以及什么数据结构对此最有效？你给我推荐什么？

此外，我担心这种情况，我的图并不总是一致的（它可能包含孤立的顶点或孤立的子图），这是 Kruskal 算法正确性的主要条件。有没有办法绕过这个问题？

感谢您提供任何帮助或提示。

4

1 回答 1

1

使用集合来构造一个Subgraph对象。子类DepthFirstIterator，以便encounterVertex将带有键v和值的条目（无论另一个端点e是什么）放入 map p。从水槽中搜索深度优先。v通过初始化为源并查找v、p[v]、等来恢复路径p[p[v]]，直到没有条目。这很痛苦，但图书馆作者FibonacciHeap融入了ClosestFirstIterator，否则这将是您想要的课程。（哎呀，如果您不关心另一个 n log n 时间操作，您可以在子图上运行 Dijkstra。）

Kruskal 的算法在不连接的图上运行良好。它返回一个最小权重生成森林，即，对于每个连接的组件，一个最小权重生成树。我不能保证这个特定的实现。

于 2013-09-04T22:05:03.017 回答