Results 1 to 1 of 1

Math Help - Algorithm to find Combinatorial Optimization of a Directed Acyclic Graph Problem

  1. #1
    Aysther
    Guest

    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.
    Last edited by Aysther; November 6th 2007 at 02:17 PM. Reason: Added image.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. directed graph question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 6th 2011, 12:10 PM
  2. Directed graph statistics
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: June 10th 2011, 12:19 PM
  3. directed acyclic graph completion time distribution
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: August 14th 2009, 11:28 PM
  4. Drawing a directed graph
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 14th 2008, 08:38 AM
  5. LINEAR OPTIMIZATION PROBLEM (Dijkstra's algorithm)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 12th 2007, 06:45 PM

Search Tags


/mathhelpforum @mathhelpforum