2

I have a graph that contains edges that must be visited, as well as edges that are optional. The edges have varying weights and can be traveled in either direction and as many times as required. I am trying to determine the route that minimises the total weight.

As I understand it, the Chinese Postman Problem deals with a graphs where every edge of a graph must be visited at least once. Can anyone tell me if the variant described above has a 'name' or point me in the direction of algorithms that might deal with solving this type of graph?

I am attempting to program a solution in Python so any solutions that use that would be great, otherwise I'm sure I will be able to work through a solution.

pppery
  • 3,731
  • 22
  • 33
  • 46
AdamDynamic
  • 761
  • 6
  • 15
  • 29
  • 2
    [`What have you tried`](http://mattgemmell.com/2008/12/08/what-have-you-tried/)? – Darin Dimitrov Feb 17 '13 at 23:13
  • 1
    show your attempted solution. – monkut Feb 17 '13 at 23:45
  • For future reference, the **Rural Postman Problem** finds a route through a set of edges _E_ such that every edge in _Eᵣ_ (where _Eᵣ_ ⊂ _E_). This is an NP-hard problem. A solution for you may be covered in [Efficient heuristics for the Rural Postman Problem (GW Groves and JH van Vuuren, 2004)](https://core.ac.uk/download/pdf/37350985.pdf). – Charlie Harding Sep 30 '20 at 09:36

0 Answers0