CODEWITHSUNDEEP
algorithmgraphgraph-theorygraph-algorithm
sandbox
sandbox

Reputation: 1

Graph Traversal Algorithm with discount

I have a directed graph with weighted edges and I would like to find the all pairs shortest paths in my graph. But I want to be able to take discounts into consideration.

For example:

A->B    with weight 10
A->C    with weight 20
B->C    with weight 10
C->D    with weight 10
A->B->C with weight 15 because I get a discount of 5 if and only if I visit B first. (see clarification)

A->B->C->D should therefor have weight 25 while
A->C->D    with weight 30

Is there a way to implement this? I have looked at various algorithms (Floyd-Warshall etc) but they dont seem to recognize this problem...

edit: to clarify: Only the combination (A->B->C) gets the discount. 

E->(A->B->C)->F gets it because it has the exact combination in its path, but 
A->E->B->C      does not get it

Upvotes: 0

Views: 270

Answers (1)

beaker
beaker

Reputation: 16809

You can augment your graph by adding edges and dummy nodes to represent the discounts. For instance, if you have a discount for the path A->B->C, add a new node B' with only the edges:

A->B'
B'->C

such that

w(A,B') + w(B',C) = w(A,B) + w(B,C) - discount

where w(S,T) is the weight of edge S->T. It doesn't matter which edge you apply the discount to, so you could have

w(A,B') = 10, w(B',C) = 5, or
w(A,B') = 5 , w(B',C) = 10

Note that if you have a node Q where the only edges incident on Q in the original graph are:

S->Q
Q->T

and a discount is to be applied for the path S->Q->T, adding a new node Q' is redundant. You can safely apply the discount to the original graph. If you add the dummy node anyway, it won't cause the results to be erroneous, or even any different, it will just add unnecessary nodes to the search.

Obviously, in the output of your paths you should treat any dummy node as their original counterpart, i.e. a path of A->B'->C should be reported as A->B->C.

Upvotes: 2

Related Questions