A recent (and also imaginary) poll conducted on a sample size of at least five 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 first 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 efficient pub crawl route through Oxford, with the help of graph theory.
First, we need to define the nodes or vertices of our graph: the pubs. Using TripAdvisor and cross referencing those results with authorities—*cough* crewdaters *cough*—we find 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 final 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 efficient solution.
The most obvious, brute-force approach of finding the shortest path through each of these pubs requires checking and comparing all possible routes from start to finish. However, with the use of some assumptions and sophisticated algorithms, we can whittle down these possibilities to just five, in other words a shortest path starting at each node.
To perform this magical reduction in possibilities it would be easiest to first look at a method of tracing a path through a graph known as a ‘breadth first 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 five, Dijkstra’s Algorithm is also a ‘greedy’ algorithm, meaning that it will always choose the next step with greatest immediate benefit 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 find 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 modification 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 five chosen pubs is of length 1.7 miles. But is it really the most efficient? Through the use of a ‘brute force approach’, we can check that the aforementioned path is, in fact, the most efficient 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?
For Cherwell, maintaining editorial independence is vital. We are run entirely by and for students. To ensure independence, we receive no funding from the University and are reliant on obtaining other income, such as advertisements. Due to the current global situation, such sources are being limited significantly and we anticipate a tough time ahead – for us and fellow student journalists across the country.
So, if you can, please consider donating. We really appreciate any support you’re able to provide; it’ll all go towards helping with our running costs. Even if you can't support us monetarily, please consider sharing articles with friends, families, colleagues - it all helps!
Thank you!
