14
$\begingroup$

Given an unweighted DAG (directed acyclic graph) $D = (V,A)$ and two vertices $s$ and $t$, is it possible to find the shortest and longest path from $s$ to $t$ in polynomial time? Path lengths are measured by the number of edges.

I am interested in finding the range of possible path lengths in polynomial time.

Ps., this question is a duplicate of the StackOverflow question Longest path in a DAG.

|cite|improve this question|||||
$\endgroup$
10
$\begingroup$

For the shortest path problem, if we do not care about weights, then breadth first search is a surefire way. Otherwise Dijkstra's algorithm works as long as there are no negative edges.

For longest path, you could always do Bellman-Ford on the graph with all edge weights negated. Recall that Bellman-Ford works as long as there are no negative weight cycles, and therefore works with any weights on a DAG.

|cite|improve this answer|||||
$\endgroup$
  • 2
    $\begingroup$ Bellman-Ford is a dynamic programming algorithm. $\endgroup$ – Raphael♦ Apr 14 '13 at 11:47
  • 1
    $\begingroup$ @Raphael yes, but I think there's a direct DP algorithm to find max path, instead of negating all the edge weights. $\endgroup$ – jmite Apr 14 '13 at 16:17
  • 1
    $\begingroup$ @jmite: Why, of course: just change Bellman-Ford to do the conversion online, or maximise, or... $\endgroup$ – Raphael♦ Apr 14 '13 at 16:19
  • 1
    $\begingroup$ By the way, I am not intuitively convinced that the NP-complete problem Longest Path is thus easily in P on DAGs. I'd appreciate a proof/reference/explanation. $\endgroup$ – Raphael♦ Apr 14 '13 at 16:22
  • 2
    $\begingroup$ Also there is a simpler and efficient DP algorithm for DAG $\endgroup$ – user742 Apr 17 '13 at 15:58
8
$\begingroup$

Let $n = |V(G)|$ and $m = |E(G)|$. Let $w(a \to b)$ denote the weight of the edge $(a \to b)$. Suppose that you want to find the minimum and maximum path cost from $s$ to $t$.

Starting from $b := t$, perform the following:

  1. If $b$ has already been visited, return the already computed $\min(b)$ and $\max(b)$. Otherwise mark $b$ as visited.

  2. Determine and record $\min(b)$ and $\max(b)$ as follows.

    • If $b = s$, store $\min(s) := \max(s) := 0$.
    • Else set $$\begin{align*}\min(b) &:= \min_{a \to b} \Bigl[ w(a \to b) + \min(a) \Bigr] \\ \max(b) &:= \max_{a \to b} \Bigl[ w(a \to b) + \max(a) \Bigr]\end{align*}$$ ignoring vertices for which $\min(a) = \max(a) = \mathrm{inaccessible}$. When computing minimum and maximum over an empty set of edges (no inbound edges to $b$ at all, or all ignored), set $\min(b) := \max(b) := \mathrm{inaccessible}$.

You should be able to prove that this algorithm runs in time $O(m)$, neglecting the time required to initialise all of the vertex variables.

|cite|improve this answer|||||
$\endgroup$
  • $\begingroup$ This recursive “pull” approach might be actually slower than the usual dynamic “push” approach and it needs a stack of linear size to handle the recursion. The usual approach is to take vertices in a topological order and improve the interim minimum and maximum for each neighbor of the current node. The current node always has the final value of minimum and maximum as all the inbound edges must have already been used to improve them. $\endgroup$ – Palec Jan 11 '15 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.