Route Inspection Problems
Chinese Postman Algorithm
- Identify all odd vertices (If all vertices are even = traversable, so add total of edges)
- If 2 odd vertices:
- Identify shortest route between them (Dijkstra)
- Double up edges on this route to give an Eulerian graph
- Add all edge weights (including new weights added in)
3. If 4 odd vertices:
- (A,B,C,D) Consider all possible pairings: AB/CD, AC/BD, AD/BC
- Choose pairing which involves adding the smallest total extra weight
- Add in extra edges and add to total