최단 경로, 2 개의 가중치 함수

Question

방향 그래프 G = (V, E), 두 개의 꼭지점 s, t 및 두 개의 가중치 함수 w1, w2가 있습니다. G에 음의 가중치 순환이 없습니다 (w1 및 w2 모두). 주어진 최단 경로 에서 s까지 t 중에서 w2만큼 s에서 t까지 최단 경로를 찾는 알고리즘을 설명해야합니다.

나는 이것을 찾았습니다 : FInding All Shortest Paths Between Two Vertices 하지만 대답은 나에게 꽤 어울립니다.

나는 이것을 해결하는 방법을 알지 못합니다 (절름발이). 도움을 주시면 감사하겠습니다.

Answer 1

아이디어는 w2을 중요하게 만들지 만, 결과는 w1입니다.

하자가 모든 가장자리에 w2의 합 SUM2 :이를 바탕으로 SUM2 = Sum { w2(e) | e in E } 및 min{w1} = min { w1(e) | e in E } (w1에 따라 최소 값)

, 새 가중치 함수 작성 : 이제

w(e) = w1(e) + w2(e)/min{w1}*(SUM2+1) 

을 제공 모든 최단 경로는 w1에 따르면 - w2에 따라 최단 경로가 선호되는 이유는 분명합니다. 한편

는 w2은 모든 가장자리의 결합 합이 w2에 따른 w1

의 단일 노드 지금보다 작다는 것을 참고하기 때문에, w1과 지배의 중요성을 극복 할만큼 '강력한'아니다 최단 경로 알고리즘을 사용하여 위의 w을 사용하여 원하는 최단 경로를 얻으십시오.