jgrapht-developers

 Re: [jgrapht-developers] all against all shortest path From: John V. Sichi - 2006-07-21 19:35:27 ```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 ```
 Re: [jgrapht-developers] [jgrapht-users] all against all shortest path From: Aaron Harnly - 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 > jgrapht-users@... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users ```