Results 1 to 1 of 1

Thread: Shortest path for a directed graph including additional variable

  1. #1
    Apr 2010

    Shortest path for a directed graph including additional variable

    I have the following graph problem for a graph with the following conditions:

    1) The graph could be disjointed
    e.g. A and B->C and D->E
    2) All edges in the graph are directed
    3) All edges have weights
    4) All edges emerging from a node will have the same weight
    e.g. in graph A->B,C
    Both A->B (weight = 1) and A->C (weight = 1)

    1) The goal is to visit all nodes using the shortest path. If the graphs are disjointed, then a path that has the least cost.
    2) Give the flexibility to split the shortest path into 2 or more (and there is a limit to the number of splits). Idea is to analyze savings by the additional split.

    To explain this better, let me give an example. Let's assume there are nodes and edges as follows:
    A->B (weight = 1)
    B->C (weight = 2)
    C->D (weight = 3)
    D->E (weight = 4)

    Now let's imagine if this was a running path from A->E taking a total time of (4+3+2+1 = 10 units). If there was one runner to run this path it would take the person 10 units of time.
    Now let's say if there were two runners. If you could introduce the another runner anywhere on the path with little or no overhead (the second runner gets a ride in the car), you could reduce overall run time.
    E.g. if Runner 1 runs from A->D (= 5 units) and Runner 2 runs from D->E (=4 units) at the same time, then overall run time is reduced to 5 units from 10 with an additional runner. Similarly with 3 people the run time could be reduced to 4 units.

    Now how to solve these two problems ?
    Last edited by ssiwani; Apr 29th 2010 at 12:43 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Little trick for shortest path
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 6th 2010, 09:37 AM
  2. Replies: 5
    Last Post: Nov 6th 2009, 05:39 PM
  3. Shortest Path - Topology
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Mar 19th 2009, 08:00 AM
  4. shortest path
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: Jan 5th 2009, 12:03 PM
  5. shortest path around cylinder
    Posted in the Geometry Forum
    Replies: 1
    Last Post: Aug 11th 2008, 09:56 PM

Search Tags

/mathhelpforum @mathhelpforum