For the past two years I have been, intermittently, working on the same problem. The difficulties of this problem are, to put it simply, are in its particulars because at heart it’s been studied since Euler’s 1736 paper on the bridges of Konigsberg. That is, it is a pathfinding problem.
It is the summer of 2012, and I have just moved out of the dorms at WKU into an apartment with four roommates not far from the bus stop at South Campus. The distance from my house to the school is under two miles and, being just as intermittently worrisome about my health as I am curious about pathfinding problems, I have knocked the rust off an old bike and taken to the sidewalks.
Stretching across the city of Bowling Green is the Green Way, a double-wide sidewalk painted to resemble a road—dashed green lines divide the concrete into two lanes. Where the Green Way merges with the road, such as at the intersection of the railroad tracks and a Waffle House, “Share the Road” signs dot the way.
Out of shape, I catch my breath at a crosswalk connecting the Green Way with the dense and irregular network of of campus sidewalks. Far fewer cars and trucks pass by than during the semester, but nonetheless there are those in a rush taking the blind curve moments after the white figure of a man walking gives me right of way to cross.
I think of Euler and his seven bridges. Although Dijkstra’s shortest path algorithm is significantly more efficient, I’ve memorized the Floyd-Warshall method because of its higher adaptability in practice at programming competitions such as ACM’s ICPC. Just as there were fewer vehicles on the streets, the summer campus favors a few employees—myself included—still on their way to their respective offices instead of its usual hustle and bustle. Free from the problems of dodging groups of pedestrians, I elect to take the direct route, that is, the shortest route across the network of sidewalks.
And I hit a wall.
Not in the sense that I had to pick myself off the ground and straighten out my handlebars, but in the sense of a project that can go no further without turning back.
That year marked the first in a multi-million dollar renovation project at WKU. Phase one, set to begin during the quiet summer of 2012, included, among the demolition of the Downing University Center, the temporary removal of sidewalks so that utility lines could be repaired or modified or amended. My shortest path now interrupted and I stopped on a long, uphill sidewalk far from the heart of campus but within a hefty stone’s throw of my office, I turn around. ∎