Longest path in ordered graph pseudocode

I try to create an algorithm to find the longest path in an ordered graph. The properties of the ordered graph are:

Each edge goes from a node with lower index to a node with a higher index. That is, every directed edge has the form (v_i, v_j) with i < j.
Each node except v_n has at least one edge leaving it. That is, for every node v_i, there is at least one edge of the form (v_i, v_j).

My first attempt is the following:

set w = v1 and L = 0
While there is edge that leaves from w
    Choose the edge (w, vj) with j as small as possible
    set w = vj and L = L + 1
return L

I cant understand why this algorithm is wrong for some cases. Can you give me an example?

Solution

My intuition tells me that just choosing the smallest j doesn't mean that somewhere else down the line the j will be continue to be the smallest.

Imagine you have a graph 1-> 3 and 1 -> 5, but 3 -> 9 and 5 -> 7 -> 9, where 9 is the last node. Your algorithm will go 1 -> 3 -> 9 which is shorter than 1 -> 5 -> 7 -> 9.

In fact, I don't think you can really just "pick" a branch and continue to follow it to the end and be correct in any case: you must check the other branches.

Recursive Approach

Here is an approach that uses a simple recursive algorithm where at each branch you calculate the length of the path and then at nodes where there are multiple branches you just return the longest.

Simple pseudocode example (in the style of Python)

class node:
    def longest_path(self):
        if len(self.children) == 0: # No children in this node
            return 1
        child_lengths = []
        for child in self.children:
            child_lengths.append(child.longest_path())
        return max(child_lengths) + 1