yunjaemu   4년 전

Graph에서 "최단"경로 탐색은 다익스트라(Dijkstra) 또는 플로이드(Floyd) 알고리즘을 주로 사용하고 있습니다.

그렇다면 "최장"경로 탐색은 DFS(깊이 우선 탐색)으로만 가능한지 궁금합니다.

다른 빠른 검색 방법이 없을까요?

jseo   4년 전

최장 단순 경로 문제는 NP-Hard 문제여서 효율적인 알고리즘이 존재하지 않습니다. 

haja   4년 전

DAG에서는 다이나믹 프로그래밍으로 O(V+E)로 풀 수 있어요.

댓글을 작성하려면 로그인해야 합니다.