CODEWITHSUNDEEP
algorithm
Collin
Collin

Reputation: 1867

Longest path in ordered graph

Let G = (V, E) be a directed graph with nodes v_1, v_2,..., v_n. We say that G is an ordered graph if it has the following properties.

Give an efficient algorithm that takes an ordered graph G and returns the length of the longest path that begins at v_1 and ends at v_n.

If you want to see the nice latex version: here

My attempt:

Dynamic programming. Opt(i) = max {Opt(j)} + 1. for all j such such j is reachable from i.

Is there perhaps a better way to do this? I think even with memoization my algorithm will still be exponential. (this is just from an old midterm review I found online)

Upvotes: 3

Views: 7163

Answers (2)

Anshul Goyal
Anshul Goyal

Reputation: 76837

Your approach is right, you will have to do 

Opt(i) = max {Opt(j)} + 1} for all j such that j is reachable from i

However, this is exponential only if you run it without memoization. With memoization, you will have the memoized optimal value for every node j, j > i, when you are on node i.

For the worst case complexity, let us assume that every two nodes that could be connected are connected. This means, v_1 is connected with (v_2, v_3, ... v_n); v_i is connected with (v_(i+1), v_(i+2), ... v_n).

Number of Vertices (V) = n

Hence, number of edges (E) = n*(n+1)/2 = O(V^2)

Let us focus our attention on a vertex v_k. For this vertex, we have to go through the already derived optimal values of (n-k) nodes.

Number of ways of reaching v_k directly = (k-1)

Hence worst case time complexity => sigma((k-1)*(n-k)) from k=1 to k=n, which is a sigma of power 2 polynomical, and hence will result in O(n^3) Time complexity.

Simplistically, the worst case time complexity is O(n^3) == O(V^3) == O(E) * O(V) == O(EV).

Upvotes: 7

notbad
notbad

Reputation: 2877

Thanks to the first property, this problem can be solved O(V^2) or even better with O(E) where V is the number of vertices and E is the number of edges. Indeed, it uses the dynamic programming approach which is quiet similar with the one you gives. Let opt[i] be the length of the longest path for v_1 to v_i. Then

opt[i] = max(opt[j]) + 1 where j < i and we v_i and v_j is connected, 
                         using this equation, it can be solved in O(V^2).

Even better, we can solve this in another order.

int LongestPath() {
   for (int v = 1; v <= V; ++v) opt[v] = -1;
   opt[1] = 0;
   for (int v = 1; v <= V; ++v) {
     if (opt[v] >= 0) {
     /* Each edge can be visited at most once,
        thus the runtime time is bounded by |E|.
      */ 
      for_each( v' can be reached from v) 
         opt[v'] = max(opt[v]+1, opt[v']);
    }
  }
 return opt[V];

}

Upvotes: 5

Related Questions