title: The Widest Path Challenge - the most efficient way for finding path in Maximal Spanning Tree
body: <p>This question is continuation of my similar earlier asked question: <a href="https://stackoverflow.com/questions/18468973/find-path-between-two-nodes-in-graph-according-to-given-criteria-optimization">Find path between two nodes in graph, according to given criteria - optimization task</a> .</p>
  
  <p><strong>Problem summary</strong>:
  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 <a href="http://en.wikipedia.org/wiki/Widest_path_problem" rel="nofollow noreferrer">"Widest path problem"</a>.</p>
  
  <p>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 <em>I need to redefine my necessities</em> 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 <a href="http://jgrapht.org" rel="nofollow noreferrer">jGraphT</a> library. It has implemented <a href="http://jgrapht.org/javadoc/org/jgrapht/alg/KruskalMinimumSpanningTree.html" rel="nofollow noreferrer">Kruskal Minimum Spanning Tree algorithm</a>. 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.</p>
  
  <p><strong>My question is following:</strong>
  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?</p>
  
  <p>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?</p>
  
  <p>Thank you for any help or tips.</p>