algorithm - 最宽路径挑战 - 在最大生成树中查找路径的最有效方法

Question

这个问题是我之前提出的类似问题的延续:Find path between two nodes in graph, according to given criteria - optimization task .

问题总结:我需要在图中找到从顶点 A 到顶点 B 的最佳路径，假设路径质量计算为路径上边权重的最小值，下一个最佳路径是具有最大最小值的路径。一般叫"Widest path problem" .

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

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

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

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

Answer 1

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

Kruskal 算法适用于断开连接的图。它返回一个最小权重生成森林，即，对于每个连接的组件，一个最小权重生成树。我不能保证这个特定的实现。