It looks like you need the shortest path for the same source and target every time. And you change a single weight each time.
topology.shortest_path return a list of edges. Why not check if the edge weight increased or decreased? There should be two cases where you don't have to recompute. One is where the edge weight decrease and that edge belongs to the list. The other case is where one weight increase and don't belong to the list. On Wed, Jan 13, 2016 at 9:07 AM, lei <[email protected]> wrote: > I want to compute shortest path repeatedly, each time some edge weight is > > changed. The following implementation run very slowly, is this my problem? > > for e in elist: > w=wt[e] > wt[g.edge_index[e]]=sys.maxint > d2=shortest_distance(g, g.vertex(s), > g.vertex(t),weights=wt) > wt[e]=w > > Profiling says most of the time (132 sec in 153 sec)is spend on > > __init__.py:539(__setitem__). > > It seems each time all weights are updated using wt, > > if there is a large number of edges, this will cost a lot time. > > But in my case, only one edge weight is changed, > > is there some other way to do this? Thanks. > > > > > > _______________________________________________ > graph-tool mailing list > [email protected] > http://lists.skewed.de/mailman/listinfo/graph-tool >
_______________________________________________ graph-tool mailing list [email protected] http://lists.skewed.de/mailman/listinfo/graph-tool
