的Python：尋找最長路徑

Question

我這樣在下面的

class Job(): 
    def __init__(self, name, weight): 
     self.name = name 
     self.weight = weight 
     self.depends = [] 

    def add_dependent(self, dependent): 
     self.depends.append(dependent) 


jobA = Job('A', 0) 
jobB = Job('B', 4) 
jobC = Job('C', 2) 
jobD = Job('D', 10) 
jobE = Job('E', 3) 
jobF = Job('F', 11) 

jobA.add_dependent(jobB) 
jobA.add_dependent(jobC) 
jobB.add_dependent(jobD) 
jobC.add_dependent(jobE) 
jobD.add_dependent(jobF) 
jobE.add_dependent(jobF) 

所以創建了一個簡單的圖形，我們有兩個可能的路徑

A->B->D->F 0+4+10+11 = 25 
A->C->E->F 0+2+3+11 = 16 

所以最長路徑將是前者

有沒有簡單的方法來收集最長的路徑A->B->D->F？

def longest_path(root): 
    paths = [] 
    # some logic here 
    return paths 

print longest_path(jobA) # should print A->B->D->F 

Answer 1

不是最有效的解決方案，但這裏是一個應該工作：

import operator 

def longest_path(root): 
    def _find_longest(job): 
     costs = [_find_longest(depend) for depend in job.depends] 
     if costs: 
      # Find most expensive: 
      path, cost = max(costs, key=operator.itemgetter(1)) 
      return ([job.name] + path, job.weight + cost) 
     else: 
      return ([job.name], job.weight) 
    return "->".join(_find_longest(root)[0]) 

Answer 2

如果使用面向對象的解決方案，可以很容易地提供一種方式來僅存儲最重的路徑。 這是我想出了一個解決方案 - 使用一個可調用的類

In [111]: class Heaviest(object): 
    ...:  def __init__(self, job): 
    ...:   self.path = '' 
    ...:   self.weight = 0 
    ...:   self.job = job 
    ...:  def _find_heaviest(self, job, path='', weight=0): 
    ...:   path += job.name 
    ...:   weight += job.weight 
    ...:   if not job.depends: 
    ...:    if weight > self.weight: 
    ...:     self.weight = weight 
    ...:     self.path = path 
    ...:   else: 
    ...:    for job in job.depends: 
    ...:     self._find_heaviest(job, path, weight) 
    ...:  def __call__(self): 
    ...:   self._find_heaviest(self.job) 
    ...:   return '->'.join(list(self.path)), self.weight 
    ...:     

In [112]: Heaviest(jobA)() 
Out[112]: ('A->B->D->F', 25) 

一個可有可無：

我突然想到昨晚，在循環依賴的情況下（見我的意見），上面會解決不會產生答案，在達到最大遞歸深度時停止例外。只要添加下面的行就會打擊任何樹遍歷算法 - 不只是這一個。

In [226]: jobF.add_dependent(jobA) 

In [227]: Heaviest(jobA)() 
--------------------------------------------------------------------------- 
RuntimeError        Traceback (most recent call last) 
<ipython-input-227-94e994624b4e> in <module>() 
----> 1 Heaviest(jobA)() 

<ipython-input-111-1ff9f69480a9> in __call__(self) 
    15     self._find_heaviest(job, path, weight) 
    16  def __call__(self): 
---> 17   self._find_heaviest(self.job) 
    18   return '->'.join(list(self.path)), self.weight 
    19 

<ipython-input-111-1ff9f69480a9> in _find_heaviest(self, job, path, weight) 
    13   else: 
    14    for job in job.depends: 
---> 15     self._find_heaviest(job, path, weight) 
    16  def __call__(self): 
    17   self._find_heaviest(self.job) 

... last 1 frames repeated, from the frame below ... 

<ipython-input-111-1ff9f69480a9> in _find_heaviest(self, job, path, weight) 
    13   else: 
    14    for job in job.depends: 
---> 15     self._find_heaviest(job, path, weight) 
    16  def __call__(self): 
    17   self._find_heaviest(self.job) 

RuntimeError: maximum recursion depth exceeded 

雖然我離開嘗試修補的實施給你 - 如果你願意 - 簡單的保護措施能夠解決這個問題

def _find_heaviest(self, job, path='', weight=0): 
    if not job.name in path: 
     path += job.name 
     weight += job.weight 
     stop_search = not job.depends 
    else: 
     stop_search = True 
    if stop_search: 
     if weight > self.weight: 

.....

問題解決

In [230]: Heaviest(jobA)() 
Out[230]: ('A->B->D->F', 25)