Visit every Node of Graph in even Parts
Question
Given an undirected Graph G having n nodes and m edges (with weights). How do I get x Paths, that visit in total all edges m from a constant starting node and return in the end, of that path, to that starting node. Nodes can be visited more than once.
- How do I write an algorithm to find those paths, that have the smallest maximum weight count. Secondly the total weight count should be minimized, but the most important part is that the highest weight count of one Path is as small as possible. The path should start from a given starting node and return after all times to that starting node.
- Is this problem NP-Complete? (I think that it is, but I'm not sure and like to know why?)
I would be very happy about any help.
Example
Given this Graph with starting point 0 and x = 4
G = [(0, 2, w=1), (0, 8, w=1), (0, 6, w=1), (0, 4, w=1), (3, 2, w=1), (2, 1 w=1),
(1, 8, w=1), (8, 7, w=1), (7, 6, w=1), (6, 5, w=1), (5, 4, w=1), (4, 3, w=1)]
the best paths would be
([0, 6, 5, 4, 0], [0, 6, 7, 8, 0],
[0, 8, 1, 2, 0], [0, 2, 3, 4, 0])
because every path has a total weight count of 4. There are no path combinations where maximum total is smaller ...