그래프가있는 그래프 순회 알고리즘

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(S,T) 가장자리 S->T의 무게

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

그. 당신에게 할인을 적용 가장자리를 중요하지 않습니다, 그래서 당신은 당신이 노드 Q이있는 경우 원래의 그래프 Q의 유일한 가장자리 사건이 어디에 있는지

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

참고 수 :

S->Q 
Q->T 

이고 경로가 S->Q->T 인 경우 할인을 적용해야하며 새 노드 Q'을 추가하면 중복됩니다. 원래 그래프에 안전하게 할인을 적용 할 수 있습니다. 어쨌든 더미 노드를 추가해도 결과에 오류가 없거나 다른 결과를 초래하지 않아 불필요한 노드를 검색에 추가하게됩니다.

분명히 경로의 출력에서 ​​더미 노드를 원래의 대응 노드로 처리해야합니다. 즉 A->B'->C의 경로는 A->B->C으로보고되어야합니다.