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

如果您使用 OO 解决方案，很容易提供一种仅存储最重路径的方法。这是我想出的解决方案 - 使用可调用的 class

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)

Python：求最长路径

Python: Finding the longest path

python

python-2.7

longest-path