글 읽기 - Graph에서 최장경로 탐색 관련

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

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

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

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

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

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

Baekjoon Online Judge