algorithm - 带折扣的图遍历算法

Question

我有一个带加权边的有向图，我想在我的图中找到所有对的最短路径。但我希望能够考虑折扣。

例如:

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

有没有办法实现这个？我看过各种算法(Floyd-Warshall 等)，但他们似乎没有意识到这个问题......

编辑:澄清一下:只有组合 (A->B->C) 才能获得折扣。

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

Answer 1

您可以通过添加边和虚拟节点来表示折扣来扩充您的图表。例如，如果您对路径 A->B->C 有折扣，请添加一个新节点 B' 仅 边缘:

A->B'
B'->C

这样

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

其中 w(S,T) 是边 S->T 的权重。将折扣应用到哪条边并不重要，因此您可以拥有

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

请注意，如果您有一个节点 Q，其中原始图中 Q 上唯一的边是:

S->Q
Q->T

并且要对路径S->Q->T应用折扣，添加新节点Q'是多余的。您可以安全地将折扣应用于原始图形。如果你无论如何添加虚拟节点，它不会导致结果错误，甚至不会导致任何不同，它只会在搜索中添加不必要的节点。

显然，在路径的输出中，您应该将任何虚拟节点视为它们的原始对应节点，即 A->B'->C 的路径应报告为 A->B->C.