CODEWITHSUNDEEP
graph-algorithm
GraphLearner
GraphLearner

Reputation: 327

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?

Upvotes: 4

Views: 44839

Answers (3)

Niema Moshiri
Niema Moshiri

Reputation: 937

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!

Upvotes: 6

algrid
algrid

Reputation: 5954

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: https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

Upvotes: 6

Flocke
Flocke

Reputation: 814

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.

Upvotes: 1

Related Questions