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

주어진 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에서) 실행하십시오.

내 솔루션이 맞습니까?

출처

2017-01-30 elias rizik

'클래식'전체 쌍 최단 경로 문제와 달리, 'u'에서 'v'까지 색상 경로가없는 'u', 'v'점이있을 수 있습니다. 연결되었다; 색상 경로가 색상 경로가 아닌 경로로 분해 될 수 있으므로 가장자리의 클래스로 인해 문제가 쉽게 분해되지 않는 것 같습니다. – Codor

공사에 대한보다 자세한 사례를 제공해 주시겠습니까? – Codor

알고리즘에 대한 설명이 이해가되지 않습니다. "모든 에지 c (v) = 3"에 대해 무엇입니까? "s에서이 경로까지의 색상 수"란 무엇입니까? – user31264

나에게 맞지 않습니다.

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

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

출처

2017-01-30 13:28:52 MSalters

정확 해 보이지만 설명은 상당히 통찰력이 있습니다. 어쨌든 나는 문제가 복잡성면에서 더 어려울 것으로 기대하고 있었다. 더 간결하게 : Dijkstra의 알고리즘은 all-paris 버전이 아닌 단일 소스 버전 용입니다. – Codor

@ 코더 : 공정한 지점; Dijkstra는 모든 경로에 비효율적입니다. – MSalters

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

답변

관련 문제