CODEWITHSUNDEEP
algorithmgraphpseudocodegreedy
Lee Yaan
Lee Yaan

Reputation: 547

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:

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?

Upvotes: 0

Views: 726

Answers (1)

Joseph Glover
Joseph Glover

Reputation: 330

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

Upvotes: 4

Related Questions