4

I know that longest/shortest path can be found in linear time by "processing the vertices in a topological order, and calculating the path length for each vertex to be the minimum or maximum length obtained via any of its incoming edges", or to put it more concisely, topologically sorting and finding the critical path.

My problem is that I need to add another restriction, which is maximum number of edges in a valid path. This complicates matters as the "maximum length obtained via any of its incoming edges" for a node may involve more edges, meaning a later higher weighted node may no longer be reachable because the maximum edges has already been reached.

What would be the correct way to go about solving this? Can it still be solved in linear time?

Acorn
  • 49,061
  • 27
  • 133
  • 172
  • 1
    I'm not sure if a linear-time algorithm exists, but there's a DP that takes time O(mk) if m = |E| and k is the maximum allowed number of edges. Let me know if I should write it up (maybe you can figure it out just from that...) – j_random_hacker May 24 '16 at 13:09
  • Are edge weights allowed to be negative? Zero? – j_random_hacker May 24 '16 at 13:29
  • 1
    It might be possible to go faster... A path of length at most k is necessarily either (a) a path of length at most RoundUp(k/2), or (b) is composed of a path of length exactly RoundDown(k/2) followed by a path of length at most RoundUp(k/2). This suggests a divide and conquer scheme where we solve 2 similar problems (one for exactly k edges, one for at most k edges) and combine them. BTW if you need a max-weight path of *exactly* k edges for k a power of 2, this can be done in O(n^2 log k) time. – j_random_hacker May 24 '16 at 13:37
  • 1
    thanks @j_random_hacker! I've posted one solution, does that align with your first comment? I'll have a think about your divide and conquer suggestion, sounds neat! Weights are all positive and greater than zero by the way. – Acorn May 24 '16 at 13:44
  • 1
    On second thought, I think we don't have to bother with shorter-than-max-possible paths at all: we can just pretend that each vertex has an unbounded-length (or even just length-k) path of 0-weight edges leading into it. That means we can now safely look for max-weight paths of length *exactly* k, which has a much simpler D&C scheme. When k is a power of 2, we have the smallest number of distinct subproblems to solve: k/2, k/4, k/8 etc. (these can be memoised and reused for solving multiple larger problems). – j_random_hacker May 24 '16 at 14:04
  • 1
    When k is not a power of 2, then in the worst case, every time we divide k by 2 we create 2 distinct subproblems RoundDown(k/2) and RoundUp(k/2). Let i = RoundDown(k/2). But fortunately the deeper subsubproblems don't proliferate: RD(i/2), RU(i/2), RD(i/2+1) and RU(i/2+1) can contain at most 2 distinct values. So in the end there are O(log(k)) subproblems even when k is not a power of 2, and overall it should be possible to solve the problem in O(n^2 log k) :) – j_random_hacker May 24 '16 at 14:15

2 Answers2

1

I think I've found a solution that makes it possible to still use topological sorting.

Do the topological sorting followed by critical path approach as normal, but when calculating the longest path to a given node, instead of just calculating one longest path, find the longest path for each path length from 1 to max edges in a valid path, creating a vertex for each of these highest scoring paths.

This basically means you explore all possible edge count variations in paths to each node, meaning the highest scoring path at the end will definitely be the longest path.

Acorn
  • 49,061
  • 27
  • 133
  • 172
  • 1
    This seems to be the DP I was thinking of, my only confusion stems from the word "vertex" in "creating a vertex for each...". I would describe the whole thing like this: for every vertex u and integer 1 <= i <= k, we want to compute the highest weight of any path of exactly i edges ending at u: call this f(u, i). It's easy to compute f(u, i) by taking the maximum of f(v, i-1) + w(v, u) over all parents v of u. – j_random_hacker May 24 '16 at 13:56
  • Thanks for the less ambiguous, more technical description! I don't have much of an algorithms background, so I'm only used to describing these things is laymanish terms. – Acorn May 24 '16 at 14:03
-1

Just run the regular algorithm. Once you find a path with the maximum number of edges, simply stop there and return the solution you've found.

Sure you can make that path even longer, but it would then invalidate the maximum number of edges so it wouldn't be a valid solution.

Sorin
  • 11,863
  • 22
  • 26
  • Having found a path with the maximum number of edges does not mean that I've found the longest path though – Acorn May 24 '16 at 12:01
  • 2
    Counterexample: The maximum weight is 10, and the graph consists of 2 paths directed away from the root: one path has 4 edges each of weight 3, the other has 2 edges each of weight 5. Not only your algorithm, but *any* algorithm for this problem that considers only subpaths of the path found by the Critical Path DP algorithm (namely, the path of weight-3 edges) will find a path of weight at most 9, though a path of weight 10 exists in the graph. – j_random_hacker May 24 '16 at 13:07