The other day I was scrolling through my LinkedIn newsfeed and saw an advertisement called IT Challenge for Charity. PostFinance set up a challenge for a charitable cause. They asked for the shortest path in the graph. In the beginning, I thought that this would be a simple task since I encounter optimization problems like these in almost every math course. So I accepted this challenge.
For the shortest direct path, I implemented Dijkstra’s algorithm in Java. I got the first result but when I submitted my solution (79.56) to the website, I was told that my result was wrong. So I suspected one has to visit all nodes to get the right result.
Travelling Salesman Problem
Words like “shortest Path” & “visiting all nodes” always reminds me of the Travelling Salesman Problem. Time is precious in times of university. To avoid having to implement an algorithm from scratch, I went looking for a Python library. Shortly, I came across mlrose. This module features various algorithms to solve optimisation problems. I picked the genetic algorithm to solve my TSP.
I ran into this issue, where their definition of a travelling salesman problem, no start and destination nodes are given. However, this problem can be easily circumvented by introducing a dummy edge between the start and destination with a path cost of zero.
mlrose unfortunately ran indefinitely and found no solution. The reason for it was that it is not possible to visit all nodes in this constellation without visiting one node twice. Another approach was needed.
With the Floyd-Warshall algorithm, all best distances to all nodes are calculated and returned as an adjacency matrix. Using this matrix one can brute force all permutations and compute the best shortest path. To keep the number of permutations small 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 would not accept my solution. So, I wrote some tests to verify my results and debug my code. But still, I could not find my mistake. After the challenge ended, I reached out to PostFinance and asked for the solution. They kindly replied and told me that the correct result would have been 79.56! So I was right all along with my first result, and their site likely had an issue with validating results.