무향 그래프를 고려하십시오. n 개의 정점과 m 개의 모서리가 있습니다. 모든 가장자리에는 그와 관련된 가중치가 있습니다.k 개의 꼭지점을 방문하는 무 방향성 그래프의 최단 경로
소스 버텍스 ', 싱크 버텍스't 및 숫자 'k'를 입력으로 사용하는 알고리즘을 장치하고 싶습니다. 알고리즘의 출력은 s와 t 사이의 k 개의 정점을 갖는 s에서 t까지의 최단 경로입니다.
좋습니다. 감사!
그래프와 연결된 [numvertices] [numvertices]의 거리 행렬을 만듭니다. 그런 다음 Floyd 알고리즘을 실행하되 그대로 numvertices 반복 대신 k 반복을 실행하십시오.
작은 연구 끝에이 문제가 NP-Hard라는 것을 알아 냈습니다. 따라서이 문제를 해결하기 위해 매개 변수화 기법을 사용해야했습니다. 내가 사용한 알고리즘은 고정 매개 변수 추적 가능한 알고리즘입니다.
나는이 문제를 해결하기 위해 내 알고리즘에 Lawler's modification of the Yen's algorithm을 사용했습니다. 엔 알고리즘은 루프없는 네트워크에서 최단 경로를 찾는 데 도움이됩니다.
매개 변수 k를 사용자로부터 (경로에있는 꼭지점의 수를) 가져 오기 : 여기 내 알고리즘은가는 방법이다. 또한 사용자가 경로를 초과하지 않아야하는 최대 거리 인 'm'을 얻습니다. 이것은 다항식 시간에 NP-Hard 문제를 푸는데 도움이되는 매개 변수입니다.
이 단계에서는 엔 알고리즘을 사용합니다. 다음 최단 경로 찾기. 경로에 k 개의 정점이 있는지 확인하십시오.
a. 예인 경우, 경로를 중단하고 반송하십시오. b. 경로의 총 거리 파라미터 'm'을 초과하면 다른 2
후 중단하고
엔 알고리즘은 최단 경로를 찾는 익스트라 알고리즘을 사용하여 '아니요 결과'를 리턴하지 않는다. 이 문제를 해결하기 위해이 알고리즘을 구현하는 것은 재미있었습니다.
가장자리에 무게가 있다고 언급했습니다. "가장자리 가중치의 최소 합계로 길이가 k + 2 인 길이에서 s까지의 경로를 찾으시겠습니까?" – mbeckish
이 무엇입니까 찾고 계십니까? http://stackoverflow.com/questions/9996808/a-shortest-path-algorithm-with-minimum-number-of-nodes-traversed – Ignacio
@mbeckish 정말 정확합니다. 더 정확하게 말하자면 s와 t 사이의 k 개의 정점을 사용하여 s에서 t까지의 경로를 찾아야합니다. 또한 경로는 s와 t 사이에 k 개의 정점이있는 다른 유사한 경로와 비교할 때 최소 합계가 있어야합니다. – eddyrokr