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:
d2=shortest_distance(g, g.vertex(s), g.vertex(t),weights=wt)
Profiling says most of the time (132 sec in 153 sec)is spend on
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.
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.
attachment.html (1.97 KB)
Joel Moberg <joel.moberg <at> gmail.com> writes:
Thanks! I will see what can be done to remove unnecessary shortest path
But I change edge weights only if they are on the shortest path, which usually
contains three or four edges. So four shortest path will cost more than 100 sec
while one shortest path computation usually costs less than 1 sec. I don't know
what went wrong.