이 문제로 정말 힘든 시간을 보내고 있습니다.
내가 그래프, 방향성 또는 무 방향성, 가중치 없음 및 순환이없는 경우. 가장 긴 경로는 어떻게 찾습니까? 내가 본 많은 알고리즘은 가중치가 적용된 그래프에 의존하고 가중치를 반전하고 bellman ford를 사용합니다. 나는 또한 동적 프로그래밍 솔루션을 보았지만 여기서 사람들은 단순히 어떤 경로를 찾고 있었으며 st에서 하나를 찾고 있습니다.
나는 그래프를 하위 문제로 나누려고 노력해 왔는데, 여기서 한 번에 하나의 노드를 추가하고 플러스 1에서 오는 부모의 값을 제공했지만 논리를 올바르게 얻을 수 없습니다.
누구든지 알고리즘을 제공 할 수 있습니까? 지수 시간은 할 수 있고 의사 다항식은 환상적입니까?
그래프가 방향성 이 있거나 방향이 지정되지 않은 경우 방향성 그래프로만 문제를 줄일 수 있습니다. 방향이 지정되지 않은 경우 v-> w 및 w-> v에서 가장자리를 만들어야합니다. 수정 된 DFS 를 사용 하여이 함수에 전달하는 노드에서 시작하는 가장 긴 경로를 측정 할 수 있습니다 . 그런 다음이 함수를 모든 노드에 실행하고 최대 값을 얻으십시오.
DFS 용 의사 코드 :
DFS(Node v):
if (v.visited?) return 0;
v.visited = true;
longestPath = 0;
foreach(Node n : v.neighbours):
longestPath = max(longestPath, DFS(n) + 1)
return longestPath
문제에 대한 의사 코드 :
longestPath(Node[] verticies):
longestPath = 0
foreach(Node v : vertices):
foreach(Node w: vertices):
w.visited = false;
longestPath = max(longestPath, DFS(v))
return longestPath;
O (n ^ 2)에서 작동하지만이 솔루션은 간단하다고 생각합니다. 알려 드리기 위해 O (n) 작동하는 솔루션이 있습니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다