Python: Finding the longest path
<p>I have a simple graph created as such in the below</p>

<pre><code>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)
</code></pre>

<p>so we have two possible paths</p>

<pre><code>A-&gt;B-&gt;D-&gt;F  0+4+10+11 = 25
A-&gt;C-&gt;E-&gt;F  0+2+3+11 = 16
</code></pre>

<p>so the longest paths would be the former</p>

<p>Is there an easy way to gather the longest path, <code>A-&gt;B-&gt;D-&gt;F</code>?</p>

<pre><code>def longest_path(root):
    paths = []
    # some logic here
    return paths

print longest_path(jobA) # should print A-&gt;B-&gt;D-&gt;F
</code></pre>

<p>Not the most efficient solution, but here is one that should work:</p>

<pre><code>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 "-&gt;".join(_find_longest(root)[0])
</code></pre>

python python-2.7 longest-path