Longest path in a graph

Given a undirected graph with vertices form 0 to n-1, write a function that will find the longest path (by number of edges) which vertices make an increasing sequence.

What kind of approach would you recommend for solving this puzzle?

3 Answers

You can transform the original graph into a Directed Acyclic Graph by replacing each of the (undirected) edges by a directed edge going towards the node with bigger number.

Then you end up with this:

I would do a Dynamic Programming algorithm. Denote L(u) to be the longest valid path starting at node u. Your base case is L(n-1) = [n-1] (i.e., the path containing only node n-1). Then, for all nodes s from n-2 to 0, perform a BFS starting at s in which you only allow traversing edges (u,v) such that v > u. Once you hit a node for which you've already started at (i.e., a node u such that you've already computed L(u)), L(s) = longest path from s to u + L(u) out of all possible u > s.

The answer to your problem is the node u that has the maximum value of L(u), and this algorithm is O(E), where E is the number of edges in your graph. I don't think you can do faster than this asymptotically

EDIT: Actually, the "BFS" isn't even a BFS: it's simply traversing the edges (s,v) such that v > s (because you have already visited all nodes v > s, so there's no traversal: you'll immediately hit a node you've already started at)

So actually, the simplified algorithm would be this:

longest_path_increasing_nodes(): L = Hash Map whose keys are nodes and values are paths (list of nodes) L[n-1] = [n-1] # base case longest_path = L[n-1] for s from n-2 to 0: # recursive case L[s] = [s] for each edge (s,v): if v > s and length([s] + L[v]) > length(L[s]): L[s] = [s] + L[v] if length(L[s]) > length(longest_path): longest_path = L[s] return longest_path

EDIT 2022-03-01: Fixed typo in the last if-statement; thanks user650654!

There are algorithms like Dijkastras algorithm which can be modified to find the longest instead of the shortest path.

Here is a simple approach:

• Use a recursive algorithm to find all paths between 2 nodes.
• Select the longest path.

If you need help with the recursive algorithm just ask.