안녕하세요 저는이 문제를 해결하기위한 최상의 알고리즘을 찾으려고합니다.전달할 의무 노드가있는 지시 가중 그래프 최단 경로
내가 지정한 시작 및 끝 노드 사이의 최단 경로를 찾아야하지만 특정 사용자 입력 노드를 통과해야하는 그래프가 있습니다.
노드를 통과해야하는 순서가 없으며 각 노드를 두 번 이상 방문 할 수 있습니다.
각 노드가 특정 순서에 도달해야 할 필요가 있다고 생각하면 각 중지에 대한 최단 경로를 먼저 계산하는 것이 더 쉽습니까?
K 최단 경로는이 문제를 해결하는 방법입니까? 최단 경로를 계산하고 거기에서부터, 모든 것이 노드를 통과해야하는 최단 경로를 찾을 때까지? 여기
제가 통과해야되는
노드 (4) 및 (6)을 그리하고 잘 알려져
1 내지 제 i가 최단 경로를 찾아야 예시 그래프 2- 이산 경로 문제 NP-complete in digraphs입니다. 그들의 증명은 그래프 G와 두 개의 소스 버텍스 s1, s2와 두 개의 터미널 t1, t2를 가진다. 작업은 두 개의 내부 정점 연결 경로 p1, p2 s.t를 찾고, p1은 s1을 t1에 연결하고 p2는 s2, t2를 연결합니다. 분리 된 경로만으로 문제를 모델링 할 수 있습니다. 위에서 언급 한 경도 증명에 제공된 그래프에서 s2, t1을 식별하고 새 정점 s2t1로 만듭니다. 그런 다음 s1에서 시작하는 경로가 s2t1을 통과하고 t2에서 끝나는 경우에만 원본 그래프에 두 개의 분리 된 경로가 있습니다. 이것은 유향 그래프에서 그러한 경로를 찾는 것조차 어렵다는 것을 의미합니다. 심지어 최적화 버전이 아닙니다.
그러나 그래프에 특수 구조가 있으면 더 쉽게 얻을 수 있습니다. 예 : 비순환 그래프에서는 더 쉽습니다.
중간 노드에서 엄격한 주문을 한 경우 올바른 것으로 간주되며 각 노드 간의 최단 경로를 순서대로 찾습니다. 주문에 신경 쓰지 않는다면 최단 경로를 사용하면 결국 답을 얻을 수 있지만 비효율적입니다. 가장 최단 경로가 아닐 수도있는 경로를 얻는 것이 괜찮은 경우 욕심 많은 알고리즘이이 경우 가장 좋은 옵션 일 수 있습니다. – Destruktor
은 다음과 유사합니다. [http://cs.stackexchange.com/questions/14977/shortest-path-that-passes-through-specific-nodes](http://cs.stackexchange.com/questions/14977/) 최단 경로 통과 특정 노드) – Destruktor
다른 질문은 비순환 그래프를 요구합니다. 또한 대답은 경로가 아닌 최단 거리입니다. –