A recent (and also imaginary) poll conducted on a sample size of at least ﬁve students revealed some interesting results. When asked to identify the keys to success at Oxford, nearly all the correspondents—apart from the two who collapsed from the stress of even hearing the word ‘succeed’—ranked ‘good grades’ at a paltry sixth position. The answer ‘battlehardened liver’ maintained its monopoly on the ﬁrst position. This is, of course, unsurprising: apart from rowing, rugby, and rowers complaining about rugby, Oxford’s favourite pastime is drinking. The 139 pubs dotted across the town are a testament to this fact.
So if you’re the type of student who only emerges from the shadows of the Bodleian past sun down, wanting to procrastinate and complain about your impending doom—sorry, deadlines—over a pint or two, look no further. Here I guide you through how to calculate the most eﬃcient pub crawl route through Oxford, with the help of graph theory.
First, we need to deﬁne the nodes or vertices of our graph: the pubs. Using TripAdvisor and cross referencing those results with authorities—*cough* crewdaters *cough*—we ﬁnd that the best pubs for a pub crawl in Oxford are: The Old Bookbinders Ale House; The White Rabbit; The White Horse; Head of the River; and the Turf Tavern. Collating the distances between all pairs of pubs on the graph, we get Table 1.
In the course of this article, we will refer to the connection between any two nodes—pubs—as an edge. The distance between any two pubs will be called the weight of the edge. Therefore, the weight of the edge between the White Horse and the Turf Tavern is 0.1 miles. Furthermore, a ‘path’ between any two nodes refers not to the physical path between the pubs, but the sequence of intermediate pubs from the pub at the source to the pub at the ﬁnal destination.
We will also be applying the condition that we will visit each edge and each pub only once, without returning to the source. While this may seem frivolous, it prevents our problem from morphing into the infamous Travelling Salesman Problem, to which there is no eﬃcient solution.
The most obvious, brute-force approach of ﬁnding the shortest path through each of these pubs requires checking and comparing all possible routes from start to ﬁnish. However, with the use of some assumptions and sophisticated algorithms, we can whittle down these possibilities to just ﬁve, in other words a shortest path starting at each node.
To perform this magical reduction in possibilities it would be easiest to ﬁrst look at a method of tracing a path through a graph known as a ‘breadth ﬁrst search’. Essentially this involves hitting the nodes adjacent to the starting pub, then the nodes adjacent to these nodes and so on. Dijkstra’s Shortest Path Algorithm does exactly the same, but with an additional distance counter that notes the shortest path to each node in the graph from the source.
While this may reduce the possibilities to just ﬁve, Dijkstra’s Algorithm is also a ‘greedy’ algorithm, meaning that it will always choose the next step with greatest immediate beneﬁt and, much like a PPE-ist in an argument, will never backtrack when wrong. Therefore, rather than making progress to the endpoint, it will meander on trying to ﬁnd the next edge with the shortest weight. Thus, we need to consider an alternate algorithm known as the Floyd-Warshall Algorithm that checks whether a node lies on the shortest path between the source and target and gives the length of this shortest path. We will run this with the small modiﬁcation that all of the pubs need to be present on this path. We get the results presented in Table 2.
Hence, we see that the shortest pub crawl between the ﬁve chosen pubs is of length 1.7 miles. But is it really the most eﬃcient? Through the use of a ‘brute force approach’, we can check that the aforementioned path is, in fact, the most eﬃcient path through all the pubs. Given that the average length of a pub crawl through these pubs is 2.68 miles with a maximum distance of 3.4 miles, we get that the chosen path is 37 per cent shorter than most paths. The downside? How many of us would have the strength or willpower to walk 0.7 miles after having visited four pubs?