Find the shortest route to visit at least once all edges of a undirected weighted non-Eulerian graph

Question

I'm trying to adress the following algorithmic problem using graph theory and Python:

I (personaly) want to find the shortest route I would follow to run through all streets of my district. I don't have the requirement to start from nor end on a particular node, I'm flexible here.

I have represented my district with a weighted undirected graph in Python using Networkx library. Edges weight being the street distance. I have 107 nodes and 130 edges. My graph is not Eulerian and I want to point out that my district has many dead-ends.

I know what I'm looking for is a variant (or equal?) to the Chinese Postman Problem but I could not find any relevant and clear process to progress...

I believe my problem is a variant of the undirected postman/chinease problem but I'm not sure how to start. In particular, I'm not sure which algorithm I could leverage.

I would be very thanksful if I could receive guidance on the approach please.

Answer 1

Thanks @Hugo! It was useful.

I was able to develop an approach and started a Python program to calculate it with inspiration from this article: https://towardsdatascience.com/chinese-postman-in-python-8b1187a3e5a

Here is the approach I followed, my graph being G:

1. Build a list containing all odd degree vertices of G
2. Generate all unique pairs of odd degree vertices of G
3. Recurcively, I generate all odd pairing combinations
4. Calculate the shortest distance of all pairs
5. Finally, the shortest route = sum of all G edges + minimum of edges that are necessary to repease (obtained from the previous step)