# Shortest path for a directed graph including additional variable

• Apr 28th 2010, 10:26 PM
ssiwani
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)

GOAL
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 ?