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:

### Like this:

Like Loading...

*Related*

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