Re: [jgrapht-developers] [jgrapht-users] all against all shortest path
Brought to you by:
barak_naveh,
perfecthash
From: Aaron H. <aa...@li...> - 2006-07-24 23:13:25
|
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 |