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 , 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:
2 responses to “ACO in Python: Shortest Paths in NetworkX”
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.
This is one nice dialogue to stumble upon 🙂