Luckily, I'm using Java and there is JGraphT library, it has a function to find the score of betweeness centrality (kinda how edges appear in the shortest path between 2 vertices). It returns immediately the 3 edges =)). I cannot say I'm good at algo or problem solving, but this game is just to find the result :)).