Algorithm to find Combinatorial Optimization of a Directed Acyclic Graph Problem
Hi Everyone. I'm looking for some help to find an algorithm that produces:
The set of N (V,K) paths through a directed acyclic graph with the smallest combined set of visited nodes. Each path has an individual maximum number of nodes visited of L(K,V) <= M, which is constant between all paths.
Where N is a predefined set of paths greater than 1, V is the starting node of each path, K is the ending node of each path, and L(K,V) is the number of nodes visited on that path. M > 1.
An example of this would be, two people carrying a deadly virus are each driving from two distinct cities, and arriving at two different distinct cities. They each need to take the route that reduces the number of cities infected (ie. they need to visit as many cities in common as possible,) minimizing the number of total cities visited, while still only making fewer than M stops each. (This needs to be able to apply to any number of people, any number of paths.)
So the product of this algorithm should be the set of optimized paths.
Hopefully this isn't too confusing. I'm trying to solve a computer optimization problem.
Dykstra's algorithm gets me part of the way there, and finds shortest individual paths, but I need to find the shortest combination of all paths, such that a minimal set of nodes is touched.