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