एक DAG

Question

में सबसे लंबे समय तक पथ एक DAG में सबसे लंबे समय तक पथ ढूंढने के लिए, मैं 2 एल्गोरिदम के बारे में पता कर रहा हूँ: algo 1: एक सांस्थितिकीय तरह कर + तरह के परिणाम पर गतिशील प्रोग्रामिंग का उपयोग ~ या ~ algo 2: गणना सभी डीएफएस का उपयोग डीएजी में पथ, और सबसे लंबे समय तक रिकॉर्ड। ऐसा लगता है कि डीएफएस के साथ सभी पथों को गिनती से बेहतर जटिलता है। क्या यह सच है?

Answer 1

आपका दूसरा विकल्प गलत है: डीएफएस, सभी संभव रास्तों का पता लगाने के नहीं है जब तक कि आपका ग्राफ एक पेड़ या एक जंगल है, और आप जड़ों से शुरू करते हैं। दूसरी एल्गोरिथ्म है कि मैं जानता हूँ कि वजन को नकारने जाता है और कम से कम पथ की खोज है, लेकिन यह top sort + DP algorithm कि आप # 1 के रूप में सूचीबद्ध की तुलना में कुछ धीमी है।

Answer 2

की गणना एक DAG के सारे रास्तों "डीएफएस" का उपयोग:

def enumerate_dag(g): 

    def enumerate_r(n, paths, visited, a_path = []): 
    a_path += [n] 
    visited[n] = 1 
    if not g[n]: 
     paths += [list(a_path)] 
    else: 
     for nn in g[n]: 
      enumerate_r(nn, paths, visited, list(a_path)) 

    paths, N = [], len(g) 
    visited = np.zeros((N), dtype='int32') 

    for root in range(N): 
    if visited[root]: continue 
    enumerate_r(root, paths, visited, []) 

    return paths 

Answer 3

नहीं डीएफएस की जरूरत है। एल्गोरिथ्म: एक DAG जी प्रत्येक चाप एक चर ई रखती

for each node with no predecessor : 
    for each of his leaving arcs, E=1. 
for each node whose predecessors have all been visited : 
    for each of his leaving arcs, E=max(E(entering arcs))+1. 

MAX_PATH किनारों के भीतर उच्चतम ई जब सभी नोड्स संसाधित किए जा चुके है लेता है।