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 <zhangl@nju.edu.cn> 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
graph-tool@skewed.de
http://lists.skewed.de/mailman/listinfo/graph-tool