Re: [jgrapht-developers] all against all shortest path
Brought to you by:
barak_naveh,
perfecthash
From: John V. S. <js...@gm...> - 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 |