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