가장 짧은 색상의 경로를 찾는 방법은 무엇입니까?

Question

주어진 G = (V, E) 모든 가장자리는이 세 가지 색상 (녹색, 빨간색, 파란색) 중 하나를가집니다. 세 가지 색상이 모두있는 경우 "색상 경로"라는 경로를 호출합니다.

Input: graph G(V,E),weight function w:E->Q+ , colored edges and vertices s . 
    output: algorithm that finds for every vertices v, a shortest path from s 
      that is Colored path 

내 해결 방법은 그래프를 살펴보고 모든 정점에 대해 경로의 개수를 계산하는 것입니다. G1, G2, G3 그래프의 복사본 3 개 생성

두 번째 그래프 (G2)의 v2에 v1을 연결하여 c (v) = 2 (c는이 경로까지의 색상 수) 에지 가중치 = 0 인 모든 에지 c (v) = 3에 대해

v2 (v2)에서 v3 (To G3)로 연결.

dijkstra를 s에서 t3까지 (G3에서) 실행하십시오.

내 솔루션이 맞습니까?

Answer 1

나에게 맞지 않습니다.

가장 쉬운 방법은 일반적인 Dijkstra에서는 각 노드에 저장할 수있는 중요한 것이 하나뿐임을 알아야합니다. 루트에서 절대 길이가 가장 짧은 경로입니다.

색상이 지정된 경로를 사용하면 모든 색상 조합에 대해 최단 경로 길이를 저장해야합니다. 따라서 3 가지 색상의 경우 가장 짧은 빨간색 경로, 가장 짧은 파란색 경로, 가장 짧은 녹색 경로, 가장 짧은 빨간색 - 파란색, 빨간색 - 녹색 및 파란색 - 녹색 경로, 마지막으로 가장 짧은 빨간색 - 녹색 경로를 저장해야합니다. 블루 경로. (총 7 가지 색상 조합).