수정 된 Dijkstra의 알고리즘

Question

우리는 0과 1 사이에있는 에지 가중치 W를 가진 유향 그래프가 제공됩니다. 소스에서 대상 노드까지의 경로 비용은 소스에서 대상 노드까지의 경로에있는 가장자리의 가중치입니다. 나는 다항식 시간에서 또는 다른 발견 적 방법을 사용하여 최소 비용 경로를 찾을 수있는 알고리즘을 알고 싶었다.

모서리 가중치 (mod 값 가져 오기)의 로그 값을 취한 다음이 그래프에 dijkstra를 적용했지만 계산할 수없는 정밀도 문제가있을 것이라고 생각했습니다.

로그 접근 방식을 개선하는 다른 방법이 있습니까?

Answer 1

Dijkstra의 알고리즘에서 노드를 방문하면이 노드에 대한 더 짧은 길이 없음을 알게됩니다. 더 많은 수의 꼭지점을 방문하면 더 작은 수를 얻을 수있는 것처럼 0,1 사이의 가중치로 가장자리를 곱하면 참이되지 않습니다.

기본적으로 이것은 그래프에서 가장 긴 경로를 찾는 것과 같습니다. 이것은 0과 1 사이의 수의 로그가 음수이므로 대수를 취하는 아이디어를 사용하여 볼 수도 있습니다. 가중치의 대수의 절대 값을 취하면 가장 긴 경로는 곱셈 그래프의 최단 경로에 해당합니다.

그래프가 비순환이면 직접 알고리즘 (Longest path problem에서 수정 됨)이 있습니다.

1. DAG의 위상적인 순서를 찾습니다.
2. 각 정점에 대해 경로 비용을 저장해야합니다. 이것을 처음에 1로 초기화하십시오.
3. 시작점에서 시작하여 토폴로지 순서대로 DAG를 이동합니다. 각 버텍스에서 모든 하위 항목을 확인하고 이전에 비해 비용이 적다면 업데이트하십시오. 가장 낮은 비용으로이 정점에 도착한 정점도 저장하십시오.

마지막 정점에 도달하면 저장된 정점을 사용하여 끝 정점에서 뒤로 이동하여 "최단"경로를 찾을 수 있습니다.

물론 그래프가 비순환 적이 지 않은 경우 무한 루프를 반복하여 언제든지 제로에 도달 할 수 있습니다.