Hmm, for a sparse graph, which I'd wager your 1% graph could be
considered, doing an iterated Dijkstra will be more efficient than
the Floyd-Warshall -- O(N E log N) vs O(N^3), if I remember right.
Other than that I don't have a clear intuition beyond John's good
idea...
good luck!
-A
--
Aaron Harnly
Center for Computational Learning Systems
Columbia University
http://harnly.net
On Jul 21, 2006, at 3:35 PM, John V. Sichi wrote:
> Muhamad Abu-Much wrote:
>> i have a undirected weighted graph, i want to find a shortest
>> path which contains the given set of nodes, or as many as possible
>> of the given
>> set.
>>
>> any idea would be appreciated
>>
>> i have implemented warshall algorithm but the all pairs solution
>> but it is time consuming since my graph is a littile bit large
>> 5552 vertices and 235222 edges.
>>
>> which iterator should i use ?, the shortest path is based on the
>> weight of the edge.
>
> There's probably a standard algorithm for this if you check a graph
> theory book. Off the top of my head, maybe you could start from the
> desired "waypoint" set and for each member, find a shortest path to
> the
> source and target independently. Link up the two halves, do that for
> each vertex in the waypoint set, and then score them based on combined
> pathlength and number of other waypoint vertices included,
> weighting the
> two in whatever way makes sense for your application.
>
> Whatever you come up with, please consider contributing it (and your
> all-pairs implementation) to JGraphT if it can be expressed
> generically.
>
> JVS
>
> ----------------------------------------------------------------------
> ---
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to
> share your
> opinions on IT & business topics through brief surveys -- and earn
> cash
> http://www.techsay.com/default.php?
> page=join.php&p=sourceforge&CID=DEVDEV
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
|
