다른 모든 홉에서 두배로 된 엣지 가중치가있는 최단 경로

그래프 가중치가 서로 또는 세 번째 홉에서 변경되는 그래프 이론 문제를 어떻게 최적으로 해결할 수 있습니까? 여전히 수정 된 Dijkstra의 알고리즘을 사용할 수 있습니까?다른 모든 홉에서 두배로 된 엣지 가중치가있는 최단 경로

출처

2017-02-12 Sauhaarda

변화하는 비용을 인코딩하는 새 그래프를 만들 수 있습니다. 실제로는 새 그래프를 명시 적으로 구성하지 않는 것이 좋습니다.

각 정점 두 정점을 일으킨다

 1 
    A --> B 
    | /| 
2 | /5 | 4 
    v < v 
    C <-- D 
    3

같은 그래프가 주어지면, 각각의 아크는 두 개의 호를 일으킨다. 원호는 원점에서 원점으로, 원점에서 원점으로 이동합니다. 이제

1   5   3 
A ---> B' B ---> C' D ---> C' 

    2   10   6 
A' ---> B B' ---> C D' ---> C 

    2   4 
A ---> C' B ---> D' 

    4   8 
A' ---> C B' ---> D

대상 또는 그 사본 저렴한 경로를 찾고, 소스 또는 첫 번째 홉이 두 배로 여부에 따라 사본 중 하나에서 검색 할 수 있습니다.

출처

2017-02-12 19:07:29

다른 모든 가장자리 무게가 두 배가됩니까? 또는 두 배가되는 모든 n 번째 홉에 적용하여 수정할 수 있습니까? 예를 들어 매 3 홉 또는 4 홉이라면? 상단에 다른 그래프를 추가하여이를 수행합니까? 나는 그것이 합리적이라고 생각한다. 정말 고맙습니다! – Sauhaarda

@Sauhaarda 각 k 번째 홉을 두 배로해야하는 그래프 (V, A)가 주어지면 꼭지점 V x {0, ..., k-1} 및 호 {(v, j)) → (w, (j + 1) mod k) | (v, j) -> (w, (j + 1) mod k)의 가중치는 (x, v, w) j = <원하는 것이면 뭐든지> else 1x. –

귀하의 게시물을 +1했지만 평판이 거의 없으므로 아무런 효과가 없었습니다. – Sauhaarda

다른 모든 홉에서 두배로 된 엣지 가중치가있는 최단 경로

답변

관련 문제