Daily Archives: December 17, 2009

ACO in Python: Shortest Paths in NetworkX

I’m supposed to be doing the final edits on the journal version of this old paper of mine (jointly with Greg Sorkin and David Gamarnik), but I’ve thought of a way to procrastinate.

Instead of checking the proofs that the length of the shortest path in my weigthed width-2 strip is \frac{p^2(1+p)^2}{(3p^2+1)} n, I’ll make a quick blog post about verifying this claim numerically (in python with networkx). This also gives me a chance to try out the new networkx, which is currently version 1.0rc1. I think it has changed a bit since we last met.

from pylab import *
from networkx import *

G = Graph()
for u, v in grid_2d_graph(100, 2).edges():
    G.add_edge(u, v, weight=rand() < .5)

wt, p = bidirectional_dijkstra(G, (0,0), (99,1))

Continue reading

2 Comments

Filed under combinatorial optimization