가중치가 변화하는 그래프의 최단 경로

Question

지역 프로그래밍 콘테스트 문제를 풀려고했습니다. 문제는 기본적으로 가중 그래프에서 최단 경로를 찾는 것입니다. 나는 이런 종류의 문제에 상당히 익숙하며 Dijkstra의 알고리즘을 사용할 수 있다고 생각했습니다. 그러나이 현재 경로의 상황에 따라 특정 값이 다릅니다.

문제 무게의 두 가지 유형이 있습니다

: 일반 중량 및 무게 조건은 (의는 K를 부르 자). 조건은 다음과 같습니다. 일단 K 가중치를 사용하여 가장자리를 이동하면 K 유형의 다른 모든 가중치는 0이됩니다. 이것은 최단 경로가 K 유형의 가중치를 가진 가장자리의 조합으로 맞출 수 있기 때문에 .

예 아래

는 이러한 유형의 문제입니다. 가중치가 변경되지 않으면 Dijkstra를 사용하여 가장 짧은 경로를 쉽게 찾을 수 있습니다. 그러나, 가중치 K가 그 값을 변경할 때, 에지 C-D의 가중치가 에지 A-C를 통해 이동 한 후에 0이기 때문에, 더 짧은 경로를 발견 할 수있다.

질문

어떻게 최단 경로를 찾을 수 있습니까?

여기 Dijkstra의 알고리즘을 사용할 수 있습니까? 아니면 A * 또는 BFS와 같은 다른 알고리즘을 사용하는 것이 더 좋습니까?

Answer 1

몇 개의 K가 있습니까?

나는 단 하나뿐입니다. Dijkstra는 좋습니다. BFS는 무게를 잘 처리하지 못한다고 덧붙일 것입니다.

알림 : Dijkstra는 정점에서 모든 정점까지의 최단 경로를 찾습니다.

Dijkstra를 두 번 실행하고 각 실행마다 다른 와이트 함수를 정의하십시오. 먼저 K 값에 대한 와이트 함수는 무한합니다. K 값에 대한 두 번째 와이트 함수는 0입니다.

run1과 run2 + K를 비교해보십시오.

가장 짧은 경로가 K가없는 경우 처음 실행하면 찾을 수 있기 때문에 이는 사실입니다. 그렇지 않으면 K와 함께 있고 두 번째 실행은 그것을 찾을 것입니다. 어느 쪽이든 알고리즘은 그것을 찾는다.