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))

Looping through that a few times can generate a plot to verify the claim in Theorem 4:

The paths themselves looks considerably cooler a on square grid instead of a width-2 strip:


Filed under combinatorial optimization

2 responses to “ACO in Python: Shortest Paths in NetworkX

  1. Greg

    Just catching up on your blog, Abie. You imagined for a moment I hadn’t already done that check in APL2? But having primitives for grid graphs and Dijkstra is quite a luxury.

  2. Dimitris Achlioptas

    This is one nice dialogue to stumble upon :-)