Längster azyklischer Pfad in einem gerichteten ungewichteten Graph

Question

Welcher Algorithmus kann verwendet werden, um den längsten Pfad in einem ungewichteten gerichteten azyklischen Graphen zu finden?

Answer 1

Dynamic programming. Es wird auch in Longest path problem verwiesen, da es sich um ein DAG handelt.

Der folgende Code aus Wikipedia:

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)) 

Answer 2

Solange der Graph azyklisch ist, alles, was Sie tun müssen, ist die Kantengewichte negieren und jede Shortest-Path-Algorithmus auszuführen.

EDIT: Offensichtlich benötigen Sie einen Algorithmus für den kürzesten Pfad, der negative Gewichtungen unterstützt. Außerdem scheint der Algorithmus von Wikipedia eine bessere zeitliche Komplexität zu haben, aber ich lasse meine Antwort hier als Referenz.

Answer 3

Wikipedia hat einen Algorithmus: http://en.wikipedia.org/wiki/Longest_path_problem

Sieht aus wie sie Gewichtungen verwenden, sollten aber mit Gewichtungen alle auf 1 gesetzt

Answer 4

durch kritische Pfad-Methode gelöst werden kann arbeiten:
1. eine topologische Ordnung finden
2. finden Sie den kritischen Pfad
siehe [Horowitz 1995], Grundlagen der Datenstrukturen in C++, Computer Science Press, New York.

Gierige Strategie (z. B. Dijkstra) wird nicht funktionieren, egal: 1. verwende "max" anstelle von "min" 2. konvertiere positive Gewichte in negative 3. Gib eine sehr große Zahl M und verwende M-w als Gewicht.