You are given a weighted directed acyclic graph G, a start node s in G. You are also given a positive integer k.
The problem is to find k directed paths starting at s, such that every node of G lies on at least one of those paths.
We consider the DAG G described below.
Let the nodes of G be the numbers 0,1,2,3,4,5,6,7,8, which we assume to be a topological ordering of the nodes. We assume that s = 0.
The following table gives the weight of the edge from i to j. There is only an edge from i to j if i < j.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 | 1 | 3 | 2 | 1 | 2 | 1 | 2 | 3 |
| 1 | 4 | 1 | 0 | 1 | 0 | 1 | 2 | |
| 2 | 3 | 4 | 3 | 4 | 3 | 2 | ||
| 3 | 1 | 0 | 1 | 0 | 3 | |||
| 4 | 1 | 0 | 1 | 2 | ||||
| 5 | 1 | 0 | 3 | |||||
| 6 | 1 | 2 | ||||||
| 7 | 3 |
For k = 1, there is only one possible solution, namely the path (0,1,2,3,4,5,6,7,8), which has cost 15.
Suppose k = 2. The two paths could be chosen to be (0,1,3,4,5,6,7) and (0,2,8). The total cost for these two paths is 11. That is not the best solution.
The best solution for k = 2 is (0,1,4,6,8) and (0,2,3,5,7) with total cost 9.
What is the best solution for k = 3?