Floyd-Warshall algorithm

[citizenfish]

I was looking to see if I could speed things up a bit as a computation on my home town of Brixham was taking 3-4 minutes.

Looking at the function get_shortest_distance_for_odd_degrees I see you are computing shortest paths on all the odd degree nodes. But I note that networkx has floyd-warshall which finds them all over the graph so I tried substituting this as follows to see if it would be quick to compute them all then pick the odd-degree nodes:-

 all_pairs_shortest_path = dict(nx.floyd_warshall(graph, weight="length"))
 
# Extract only the odd-degree node pairs
 return {(v, u): all_pairs_shortest_path[v][u] for v, u in combinations(odd_degree_nodes, 2)}

This significantly improved performance from over 2 minutes to 24 seconds. Testing with Brixham it seems to work OK but I'm not a graph theory expert, my maths degree is a distant memory. I'm just adding as an issue for information.