PostFinance Challenge
I spotted the IT Challenge for Charity on LinkedIn — PostFinance had set up a graph optimization challenge for a charitable cause. Find the shortest path. Simple enough, I thought, since I run into optimization problems like this in almost every math course. So I jumped in.
Dijkstra’s algorithm
I started with Dijkstra’s algorithm in Java for the shortest direct path. My result came out to 79.56, but the website rejected it. I suspected the challenge required visiting all nodes.
Travelling Salesman Problem
Words like “shortest path” and “visiting all nodes” always remind me of the Travelling Salesman Problem. Time is precious during university, so to avoid implementing an algorithm from scratch, I went looking for a Python library. I soon came across mlrose. The module offers various algorithms for optimisation problems, so I picked the genetic algorithm to solve my TSP.
I ran into an issue: in their definition of the travelling salesman problem, no start and destination nodes are given. I worked around this by introducing a dummy edge between the start and destination with a path cost of zero.
Unfortunately, mlrose ran indefinitely and never found a solution. The problem was that this particular graph can’t be traversed without visiting at least one node twice. I needed a different approach.
Floyd-Warshall
The Floyd-Warshall algorithm calculates the shortest distances between all pairs of nodes and returns them as an adjacency matrix. From there, I could brute-force all permutations to find the optimal path. To keep the number of permutations manageable, I divided the graph into subgraphs.
Shortest Path - Visiting all
Subgraph 1: 35.03432834262672
Subgraph 2: 38.39545497883789
Subgraph 3: 49.310871849778685
Subgraph 4: 51.43259519936775
Best Sum: 174.17325037061107
Sadly, the submission site still rejected my solution. I wrote tests to verify my results and combed through my code, but couldn’t find the mistake. After the challenge ended, I reached out to PostFinance and asked for the correct answer. They replied: 79.56. My very first Dijkstra result had been right all along — their validation site was the one with the bug.