与えられた重み付けされていないグラフを与え、最大長さの単純なパスを見つけることは です(開始頂点と終了頂点は固定されません)。明らかにO(n^2 * 2^n)で解くことができますが、わからないO(n * 2^n)アルゴリズムがあると聞きました。だから、それをO(n * 2^n)で解く方法は? // n = | V |最大経路問題
Q
最大経路問題
4
A
答えて
5
あなたの問題は本当にDAGにLongest Path Problemであれば、ウィキペディアからのアルゴリズムは以下であるとOで実行されます(| V | + | E |):
algorithm dag-longest-path is
input:
Directed acyclic graph G
output:
Length of the longest path
length_to = array with |V(G)| elements of type int with default value 0
for each vertex v in topOrder(G) do
for each edge (v, w) in E(G) do
if length_to[w] <= length_to[v] + weight(G,(v,w)) then
length_to[w] = length_to[v] + weight(G, (v,w))
return max(length_to[v] for v in V(G))
関連する問題
- 1. 保存画像経路問題
- 2. PostgreSQL - 最短経路
- 3. Networkx - 最短経路長
- 4. 地下最短経路 - Java
- 5. 最短経路変更
- 6. O(E)最短経路
ウィキペディアは、この問題がある非循環グラフのために言いますO(| V | + | E |)である。グラフにサイクルがありますか? (ref:http://en.wikipedia.org/wiki/Longest_path_problem) – jtdubs
@jtdubsこのコメントは実際に正しい答えではありませんか? – bbaja42
また、グラフにサイクルがある場合。 D – bbaja42