1
this algorithm을 사용하면 가중치를 적용한 DAG에서 최장 경로를 찾을 수 있습니다 (토폴로지 정렬을 사용하고 각 가장자리를 완화). 내 질문은 이제 DAG의 상위 3 개 최장 경로를 찾는 알고리즘이 있다면 무엇입니까? 또는,이 알고리즘을 구현하는 자바 스크립트 또는 자바 라이브러리가 있습니까?유향 비순환 가중 그래프에서 최상위 3 개의 최장 경로 찾기
A
답변
0
당신은 쉽게 첫번째 긴 경로를 계산 할 수 있으며, 다음 긴 경로를 찾는 알고리즘을 다음 사용할 수 있습니다 : 다시 긴 찾을
한 및 실행 알고리즘에 의해 주요 긴 경로 하나의 각 가장자리 삭제를 수정 된 그래프의 경로를 클릭 한 다음 삭제 된 모서리를 되돌리고 다른 모서리 하나를 삭제합니다.
왜 작동합니까?
경로는 첫 번째 가장 긴 경로가 아니므로 두 번째로 긴 경로가 적어도 하나의 가장자리에서 달라야하므로 한 가장자리를 무시하고 결국 찾을 수있는 각 가장자리의 가장 긴 경로를 찾으십시오 주된 최장 경로와 적어도 하나의 가장자리를 공유하지 않는 가장 긴 경로.
세 번째로 긴 경로는 가장 긴 경로이며 첫 번째 경로와 두 번째로 긴 경로와 최소한 하나의 가장자리를 공유하지 않는 경로입니다.
내가 틀릴 수도 있지만이 작업을 수행하는 유일한 알고리즘은 가능한 모든 경로를 생성하고 경로 길이별로 정렬 한 다음 원하는 경로를 선택하는 것입니다. 가장 긴 경로를 찾은 다음 그래프를 수정하여 경로가 상위 3 개에 더 이상 존재하지 않지만 다른 경로는 수정하지 않고 반복합니다. 일반적으로 가능하지는 않지만, 그래프의 특정 하위 클래스가있을 수도 있지만 가능할 수도 있습니다. – twalberg
지금 당장은 내 생각을 말할 시간이 충분하지 않지만 3 일 만에 더 많은 설명을 드리겠습니다. 주 아이디어는 하나 이상의 가장자리를 가장 긴 가장 긴 경로와 공유하지 않는 가장 긴 경로를 찾아야한다는 것입니다 따라서 그래프의 알고리즘에서 주 긴 경로의 각 가장자리를 뺀 값을 실행하면됩니다. – FazeL