[jgrapht-users] Dijkstra, FloydWarshall or Edmonds?

[André K. <akr...@on...>]

Hello,
 
I would apreciate some help with using jgrapht. 
 
Here's my task:
 
I have created a acyclic SimpleDirectedWeightedGraph where the edge weights
can be interpreted as cost to visit the target vertex.
 
The graph has a single source and several sinks. Usually there are several
hundred vertices in the graph.
 
Now I want to find the path from the source to a sink vertex that produces
the minimum average cost.
 
That is not necessarily the shortest path, I think it is the path where the
sum of all weights divided by the length of the path is minimized.
 
However, i first used Dijkstras algorithm to solve the problem. For every
sink vertex i get the (Dijkstra-) shortest path from source to sink and
calculate the minimum costs by inspecting the edge list of the path.
 
I compared that solution to the FloydWarshall algorithm. In contrast to
Dijkstra it finds the shortest path's between ALL vertices of the whole tree
in one flow. The minimum cost must still be found by inspecting the
resulting edge list of every shortest path from source to sink.
 
The result of the comparison seems obvious. FloydWarshall is faster than
Dijkstra if only a few vertices are in the tree. The advantage of using
Dijkstra: I only need to calculate the path's from source to sink.
 
BUT: I think there must be a much better way to solve this kind of problem.
In fact this seems to be a 'optimum branching' problem as described here:
http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm
 
Am I right? What is the best way to solve this by using jgrapht? 
 
Thanks in advance, 
 
André