Solving Graph Problems with City Bikes of Helsinki
I like casual biking and some algorithms. What I especially like are the City bikes of Helsinki. The network of stations allows you to conveniently travel in the city center as you can take and return a bike in any station. The bike station network also gives a nice context to solve some well-known graph problems.
In this blog post the following problems are addressed with well-known algorithms: Shortest path, Minimum spanning tree and Travelling salesman problem. The focus will be on the visualization of the algorithms.
Creating the graph
In real life you could travel directly between any two stations, so there would be an edge from each of the stations to every station. However, the visualization of the graph would be inconvenient, since it would be overwhelmed with edges. Because of this the graph was created in such a way that you can travel only to the 7 nearest stations from each station.
Dijkstra’s algorithm is probably the most known method to solve the distance between two nodes in a graph. In this implementation of Dijkstra, when a node is visited, all its neighbor nodes are added to a priority queue, with a priority of the current distance to that node. The next node that will be visited is then extracted from the priority queue. Every time an unvisited node is reached, the current distance to that node must be the shortest possible.
Minimum spanning tree
Minimum spanning tree (MST) is the shortest tree in which every node is contained. In this context, the MST could represent e.g. the minimun number of cable required to get a connection from every station to another station. We will use Kruskal’s algorithm to generate the MST.
The algorithm works by first sorting all edges by distance. The edges are then added to the graph starting from the shortest. However, if the edge would result a cycle in the graph, it will be discarded. When all nodes are contained in the tree, we can terminate the algorithm and the resulting set of edges is the MST.
Travelling salesman problem
In the Travelling salesman problem (TSP), the problem is to find the shortest tour in such a way that all the nodes are visited. It turns out there is there is no polynomial time algorithms to solve this problem. Even verifying that a given solution is correct requires exponential time. ( NP-hardness )
TSP is quite a popular problem, since it’s very easy to grasp, but difficult to solve. We will solve the TSP using two approximation approaches: a greedy algorithm and minimum spanning tree with shortcuts. These algorithms will not produce the shortest tour, but will run in a decent time to produce meaningful visualizations.
Travelling salesman: Greedy algorithm
The greedy algorithms is simple: We just choose the closest unvisited node. It can be easily seen that the resulting route is not optimal.
Here is cool video I found that shows some further optimizations on top of the greedy algorithm.
Travelling salesman: MST + shortcuts
In this approximation we first calculate the minimum spanning tree and then traverse that tree in pre-order. This results a tour in which every node is visited. We also use possible shortcuts.
The resulting algorithm in the context of City bike stations is shown below. The blue lines represent the MST, which is traversed. In this visualization, the shortcut is drawn directly between the two nodes, even though such edge would not exits in the graph.
Graph algorithms +”real-life” graph gives a nice context to visualize the logic of some well-known algorithms. In many cases, a visualization can provide a better understanding of the general concept of an algorithm than the pseudocode or implementation. You can check the provided codepens, if you want to examine more closely, how the algorithms were really implemented.