The Widest Path Challenge - the most efficient way for finding path in Maximal Spanning Tree

Question

This question is continuation of my similar earlier asked question: Find path between two nodes in graph, according to given criteria - optimization task .

Problem summary: I need to find the best path in graph from vertex A to vertex B, with assumption, that path quality is calculated as min value of edge weight on path and next the best path is that, which has max min value. Generally it's so called "Widest path problem".

Previously I needed to solve this problem in very small graph (up to 15 vertices), so I didn't need sophisticated algorithm and with the help of kind peoples, I have designed my working algorithm. Unfortunately now I need to redefine my necessities in such way, that my graph can be very large (even 50 thousands of edges). I'm aware that I need to find Maximal Spanning Tree for my graph and obtain a simple path from start to stop vertex in obtained MST. I have decided to use jGraphT library. It has implemented Kruskal Minimum Spanning Tree algorithm. I can obtain Maximal Spanning Tree by multiplying each edge weight by (-1) and using Kruskal for Minimal Spanning Tree, but algorithm in the library has been designed for retrieving Hash Set of MST edges.

My question is following: I have obtained Maximal Spanning Tree of graph as java HashSet of edges. How I can find a path from vertex A to vertex B in such structure in the most efficient way and what data structure will be the most efficient for this purpose? What do you recommend me?

Additionally, I'm worried about such situation, that my graph is not always consistent (it may contain isolated vertices or isolated subgraphs), what is main condition for Kruskal algorithm correctness. Is it any way to bypass this problem?

Thank you for any help or tips.

Answer 1

Use the set to construct a Subgraph object. Subclass DepthFirstIterator so that encounterVertex puts an entry with key v and value (whatever the other endpoint of e is) into a map p. Search depth-first from the sink. Recover the path by initializing v to be the source and looking up v, p[v], p[p[v]], etc., until there is no entry. This is a pain, but the library authors baked FibonacciHeap into ClosestFirstIterator, which otherwise would be the class you want. (Heck, if you don't care about another n log n time operation, you could just run Dijkstra on the subgraph.)

Kruskal's algorithm functions fine with disconnected graphs. It returns a minimum-weight spanning forest, i.e., for each connected component, a minimum-weight spanning tree. I can't vouch for this particular implementation.