slow shortest path

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.

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

computations.

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.