Re: [jgrapht-users] Dijkstra, FloydWarshall or Edmonds?

[Joris K. <de...@gm...>]

Hey,

If I understand you correctly, you are not looking for the cheapest
path, which is provided by Dijkstra's algorithm, nor are you
interested in finding the shortest path to each vertex
(FloydWarshall). What you do want to find is the path with the lowest
average cost, where the average cost is defined as: sum the cost of
all edges in the path and divide by the number of edges.
As you conclude yourself, this is not necessary the shortest path.
Take for example the following two paths from source to a sink:
Path 1: cost: 4, length 1
Path 2: cost: 5, length 2

Obviously, the cheapest path is Path 1, but the path with the lowest
average edge cost is Path 2.

There is an easy way to implement this, but not with branch and bound
(because you cannot bound), using a modified version of Dijkstra's
shortest path algorithm. Since this looks like a school assignment,
I'm not going to give you a final solution, but I can give you some
hints.

Have a look at the pseudo code of Dijkstra's shortest path:
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
As you can see, this algorithm tries to find the shortest path from a
source to any destination. As soon as the target destination is found,
the algorithm terminates. So what you have to do is alter the
implementation of Dijkstra's algorithm a bit as follows:
1. In the original Dijkstra, the distance d(u,v) from vertex u to v,
equals the sum of the edge cost in the path from u to v. You have to
change this path cost to the average path cost, which is the sum of
the edge cost in the path from u to v divided by the path length.
2. You have to continue the algorithm until the entire graph has been
explored. You cannot stop once you have found the first sink (think
about this: bounding is not possible)! As soon as the entire graph has
been explored, you simply iterate over your sinks, until you have
found the one with the lowest average cost.

Hope this helps,

br,

Joris


On Sun, Apr 4, 2010 at 1:10 PM, André Kreienbring
<akr...@on...> wrote:
> 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é
>
> ------------------------------------------------------------------------------
> Download Intel&#174; Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>