Python: Finding the longest path

Question

I have a simple graph created as such in the below

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)

so we have two possible paths

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

so the longest paths would be the former

Is there an easy way to gather the longest path, 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

Not the most efficient solution, but here is one that should work:

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