<p>Without further information on how the costs can vary, the problem is NP-complete. For instance, consider the following rule for setting costs:</p>

<ul>
<li>If an edge would return to a previously-traversed node then its cost is $n$</li>
<li>If an edge reaches $t$ without previously traversing all other nodes then its cost is $n$</li>
<li>In all other cases the cost of an edge is $1$.</li>
</ul>

<p>For such a rule, a Hamiltonian path has cost $n-1$ and all other paths have cost $n$ or greater. The problem could still be solved more efficiently than a brute-force search (e.g. in time $O(n^22^n)$ by dynamic programming) but not in polynomial time unless $\mathsf{P}=\mathsf{NP}$.</p>

<p>So if you want to find a polynomial time algorithm you will need to be much more specific about what sort of dependence between edge cost and previous path information is allowed.</p>

CC BY-SA 3.0
2015-05-18T16:47:44.213Z
The underlying digraph is acyclic, which makes the Hamiltonian path problem tractable.
Gamow
CC BY-SA 3.0
2015-05-18T18:25:26.907Z
Good point. But all that means is that we have to use the same costs on a DAG that has $n$ copies of each vertex, and that replaces each edge $uv$ in a hard instance of Hamiltonian paths with $n-1$ edges $u_iv_{i+1}$ between copies of the same vertices in the expanded DAG.
David Eppstein
CC BY-SA 3.0
2015-05-19T09:26:44.923Z
Why the path has to be hamiltonian?
Felipe Rojas
CC BY-SA 3.0
2015-05-19T16:34:25.350Z
Because any other path would be longer.
David Eppstein
CC BY-SA 3.0
2015-05-16T19:04:38.450Z
2015-05-16T23:56:35.447Z
2015-05-16T23:56:35.447Z
David Eppstein
<p>Although this question does not seem research-level, here is a solution that does not check all possible paths (elaborating on the above comment).</p>

<p>The naive dynamic programming approach is to use a 6-dimensional table $(x,y,min_p,max_p,min_t,max_t)$, storing the cost of the minimum path to node $(x,y)$, such that the minima and maxima since the last checkpoint are $(min_p,max_p,min_t,max_t)$.</p>

<p>Since there are $m+n$ candidate values for each minimum and maximum, this table may be huge, namely size $O(m\cdot n\cdot (m+n)^4)$.
You can implement this using a hash-table, mapping each $(x,y,min_p,max_p,min_t,max_t)$.</p>

<pre><code>// T[x,y,min_p,max_p,min_t,max_t] will eventually contain:
// the minimum cost of a path (excluding the cost since the last checkpoint) to node (x,y)
// such that the minimum P.p or Q.p since the last checkpoint of that path is min_p, etc.
T = empty hash table
for x in [0..m-1]
  for y in [0..n-1]
    for min_p in P.ps + Q.ps
      for max_p in P.ps + Q.ps
        for min_t in P.ts + Q.ts
          for max_t in P.ts + Q.ts
            T[x,y,min_p,max_p,min_t,max_t] = infinity
// there is only one path to (0,0)
// if we don't count the cost since the last checkpoint, this path has cost 0
T[0,0,min(P[0].p,Q[0].p),max(P[0].p,Q[0].p),...] = 0
for x in [0..m-1]
  for y in [0..n-1]
    for min_p in P.ps + Q.ps
      for max_p in P.ps + Q.ps
        for min_t in P.ts + Q.ts
          for max_t in P.ts + Q.ts
            cost_to_xy = T[x,y,min_p,max_p,min_t,max_t]
            // try advance P
            if x&lt;m-1
              key = (x+1,y,min(min_p,P[x+1].p),max(max_p,P[x+1].p),...)
              T[key] = min(T[key], cost_to_xy)
            // try advance Q
            if y&lt;n-1
              key = (x,y+1,min(min_p,Q[y+1].p),max(max_p,Q[y+1].p),...)
              T[key] = min(T[key], cost_to_xy)
            // try advance both (checkpoint)
            if x&lt;m-1 and y&lt;n-1
              key = (x+1,y+1,min(P[x+1].p,Q[y+1].p),max(P[x+1].p,Q[y+1].p),...)
              T[key] = min(T[key], cost_to_xy + max_t-min_t + max_p-min_p)
</code></pre>

<p>The cost of the optimal path is then the minimum over all
$T[m-1,n-1,min_p,max_p,min_t,max_t] + max_t - min_t + max_p - min_p$</p>

<p>Disclaimer: This solution is not at all optimized and you still have to fill some blanks. Neither does it give you the actual path, but you can get it with some small tweaks.</p>

CC BY-SA 3.0
2015-05-21T20:16:07.563Z
2015-05-21T20:16:07.563Z
Tim
<p>I've got the following problem</p>

<p>Consider a DAG $G=(V,E)$ with $V=[v_1,…,v_n]$, and edge-set $E=[e_1,…,e_m]$, with associated costs $c_1,…,c_m$. The problem is to find the shortest paths from an initial vertex $s$ to multiple targets $t_1,…,t_k$, taking into account these costs. A typical shortest path problem.</p>

<p>However, my problem is slightly different:
the costs $c_1,…,c_m$ depend on the previously traversed nodes
Is there an alternative to the brute-force solution: find all the simple paths between $s$ and $t$ and then select the one with the lowest cost?</p>

<p>Path can be compared.
Take as example the following graph:
Red arcs are "checkpoint arcs". All the sub-paths having a red arc as last one can be compared, so a local decision can be taken. Similarly, costs are reset after traversing such arcs: 22->23 has a different cost if the subpath includes the arc 11->22 or not.</p>

<p><img src="https://i.sstatic.net/jc7jb.png" alt="enter image description here"></p>

<p>EDIT 2:</p>

<p>Costs are related to two sequences: $P$ and $Q$, where $len(P)=N$ and $len(Q)=M$. In the aforementioned case $M=N=4$.
Each element of $P$ and $Q$ is a tuple $(t,p)$. The tuple ($t_i,p_i)$ is the ith tuple of the sequence. Tuples are constrained on $t$: $t_{i+1} &gt; t_i$. There's no constraint on $p$.</p>

<p>Let $s_p$ a set of valid indices for the sequence $P$ and $s_qp$ a set of valid indices for the sequence $Q$. The cost $C(s_p,s_q)= C_t(s_p,s_q)+C_q(s_p,s_q)$ where $C_t = max(max(P[s_p][t]),max(Q[s_q][t])) - min(min(P[s_p][t]),min(Q[s_q][t]))$ and $C_p = max(max(P[s_p][p]),max(Q[s_q][p])) - min(min(P[s_p][p]),min(Q[s_q][p]))$</p>

<p>The cost $C(s_p,s_q)$ represents the "diameter" of the element obtained by merging the $s_p$th elements of $P$ and the $s_q$th elements of $Q$. </p>

<p>Each path in the graph builds different $s_p$ and $s_q$ sets.
For example, the path 00,11,22,33 has a cost $C_{tot} = C(0,0)+ C(1,1)+ C(2,2)+ C(3,3)$, while the path 00 - 01 - 12 - 22 - 33 has a cost $C_{tot} = C(0,[0,1])+ C([1,2],2)+ C(3,3)$</p>

CC BY-SA 3.0
2015-05-16T17:26:09.277Z
Do the costs depend on all previously traversed nodes (so there are an exponential number of potential costs)?  If so, how are they given?
SamM
CC BY-SA 3.0
2015-05-18T19:38:47.100Z
Your question as stated is not answerable.  The only useful answer is "It depends".  It depends on how the cost of the path is defined.  There are some cost functions where you can't do any better than enumerating all paths; and others where you can do vastly better.  So, please edit the question to specify this necessary information.
D.W.
CC BY-SA 3.0
2015-05-19T09:26:24.217Z
I edited the question adding the needed information
Felipe Rojas
CC BY-SA 3.0
2015-05-19T22:35:59.090Z
Thanks for the added info. It seems that one of the sets $s_p$ and $s_q$ is always a contiguous sequence of indices while the other is a singleton. So you can easily compute all $C(i,[j,...,k])$ as well as $C([i,...,j],k)$. From there, you can compute the shortest path in $O(nm(n+m))$ time. However, using dynamic programming, I think you can actually compute the minimum $C_{tot}$ in $O((n+m)^2)$ time.
Tim
CC BY-SA 3.0
2015-05-20T07:28:12.330Z
Thanks Tim.So, you're suggesting to precompute all the possible $C$ values? Actually, $s_p$ and $s_q$ can be both contiguous sequences: take as example the path 00->01->11. $C_{tot}=C([0-1],[0-1])$, and there's no guarantee that the direct path 00-11 ($C_{tot}=C(0,0)+C(1,1)$ has a lower cost (because the cost on the $p$ component could be higher)
Felipe Rojas
CC BY-SA 3.0
2015-05-20T17:25:10.283Z
I see what you mean now. In that case the naive dynamic programming approach would be using a 6-dimensional table $(x,y,\min_p,\max_p,\min_t,\max_t)$, storing the cost of the minimum path to node $(x,y)$, such that the minima and maxima since the last checkpoint are $(\min_p,\max_p,\min_t,\max_t)$.
Since there are $m+n$ candidate values for each minimum and maximum, this table may be huge, but at least gives a polynomial time algorithm. There may be more efficient ways though.
Tim
CC BY-SA 3.0
2015-05-21T14:06:19.427Z
Thanks for the comment, Tim. However, I still don't get how to implement this.The solution you propose is to break the problem into many subproblems, trying to find the best path between checkpoints, right?
Felipe Rojas
<graph-theory><graph-algorithms><directed-acyclic-graph>
Shortest path in DAG with path dependent arc costs
Felipe Rojas
# Shortest path in DAG with path dependent arc costs

(Asked by: username_0 on 2015-05-16)

I've got the following problem

Consider a DAG $G=(V,E)$ with $V=[v\_1,…,v\_n]$, and edge-set $E=[e\_1,…,e\_m]$, with associated costs $c\_1,…,c\_m$. The problem is to find the shortest paths from an initial vertex $s$ to multiple targets $t\_1,…,t\_k$, taking into account these costs. A typical shortest path problem.

However, my problem is slightly different:
the costs $c\_1,…,c\_m$ depend on the previously traversed nodes
Is there an alternative to the brute-force solution: find all the simple paths between $s$ and $t$ and then select the one with the lowest cost?

Path can be compared.
Take as example the following graph:
Red arcs are "checkpoint arcs". All the sub-paths having a red arc as last one can be compared, so a local decision can be taken. Similarly, costs are reset after traversing such arcs: 22->23 has a different cost if the subpath includes the arc 11->22 or not.

![enter image description here](https://i.sstatic.net/jc7jb.png)

EDIT 2:

Costs are related to two sequences: $P$ and $Q$, where $len(P)=N$ and $len(Q)=M$. In the aforementioned case $M=N=4$.
Each element of $P$ and $Q$ is a tuple $(t,p)$. The tuple ($t\_i,p\_i)$ is the ith tuple of the sequence. Tuples are constrained on $t$: $t\_{i+1} > t\_i$. There's no constraint on $p$.

Let $s\_p$ a set of valid indices for the sequence $P$ and $s\_qp$ a set of valid indices for the sequence $Q$. The cost $C(s\_p,s\_q)= C\_t(s\_p,s\_q)+C\_q(s\_p,s\_q)$ where $C\_t = max(max(P[s\_p][t]),max(Q[s\_q][t])) - min(min(P[s\_p][t]),min(Q[s\_q][t]))$ and $C\_p = max(max(P[s\_p][p]),max(Q[s\_q][p])) - min(min(P[s\_p][p]),min(Q[s\_q][p]))$

The cost $C(s\_p,s\_q)$ represents the "diameter" of the element obtained by merging the $s\_p$th elements of $P$ and the $s\_q$th elements of $Q$.

Each path in the graph builds different $s\_p$ and $s\_q$ sets.
For example, the path 00,11,22,33 has a cost $C\_{tot} = C(0,0)+ C(1,1)+ C(2,2)+ C(3,3)$, while the path 00 - 01 - 12 - 22 - 33 has a cost $C\_{tot} = C(0,[0,1])+ C([1,2],2)+ C(3,3)$

**Tags:** graph-theory, graph-algorithms, directed-acyclic-graph

> **Comments:**
> **username_1**: Do the costs depend on all previously traversed nodes (so there are an exponential number of potential costs)?  If so, how are they given?  
> **username_2**: Your question as stated is not answerable.  The only useful answer is "It depends".  It depends on how the cost of the path is defined.  There are some cost functions where you can't do any better than enumerating all paths; and others where you can do vastly better.  So, please edit the question to specify this necessary information.  
> **username_0**: I edited the question adding the needed information  
> **username_3**: Thanks for the added info. It seems that one of the sets $s_p$ and $s_q$ is always a contiguous sequence of indices while the other is a singleton. So you can easily compute all $C(i,[j,...,k])$ as well as $C([i,...,j],k)$. From there, you can compute the shortest path in $O(nm(n+m))$ time. However, using dynamic programming, I think you can actually compute the minimum $C_{tot}$ in $O((n+m)^2)$ time.  
> **username_0**: Thanks username_3.So, you're suggesting to precompute all the possible $C$ values? Actually, $s_p$ and $s_q$ can be both contiguous sequences: take as example the path 00->01->11. $C_{tot}=C([0-1],[0-1])$, and there's no guarantee that the direct path 00-11 ($C_{tot}=C(0,0)+C(1,1)$ has a lower cost (because the cost on the $p$ component could be higher)  
> **username_3**: I see what you mean now. In that case the naive dynamic programming approach would be using a 6-dimensional table $(x,y,\min_p,\max_p,\min_t,\max_t)$, storing the cost of the minimum path to node $(x,y)$, such that the minima and maxima since the last checkpoint are $(\min_p,\max_p,\min_t,\max_t)$. Since there are $m+n$ candidate values for each minimum and maximum, this table may be huge, but at least gives a polynomial time algorithm. There may be more efficient ways though.  
> **username_0**: Thanks for the comment, username_3. However, I still don't get how to implement this.The solution you propose is to break the problem into many subproblems, trying to find the best path between checkpoints, right?  

---

## 2 answers

### Answer by username_4 on 2015-05-16. Score: 6

Without further information on how the costs can vary, the problem is NP-complete. For instance, consider the following rule for setting costs:

* If an edge would return to a previously-traversed node then its cost is $n$
* If an edge reaches $t$ without previously traversing all other nodes then its cost is $n$
* In all other cases the cost of an edge is $1$.

For such a rule, a Hamiltonian path has cost $n-1$ and all other paths have cost $n$ or greater. The problem could still be solved more efficiently than a brute-force search (e.g. in time $O(n^22^n)$ by dynamic programming) but not in polynomial time unless $\mathsf{P}=\mathsf{NP}$.

So if you want to find a polynomial time algorithm you will need to be much more specific about what sort of dependence between edge cost and previous path information is allowed.

> **Comments:**
> **username_5**: The underlying digraph is acyclic, which makes the Hamiltonian path problem tractable.  
> **username_4**: Good point. But all that means is that we have to use the same costs on a DAG that has $n$ copies of each vertex, and that replaces each edge $uv$ in a hard instance of Hamiltonian paths with $n-1$ edges $u_iv_{i+1}$ between copies of the same vertices in the expanded DAG.  
> **username_0**: Why the path has to be hamiltonian?  
> **username_4**: Because any other path would be longer.  

---

### Answer by username_3 on 2015-05-21. Score: 0

Although this question does not seem research-level, here is a solution that does not check all possible paths (elaborating on the above comment).
The naive dynamic programming approach is to use a 6-dimensional table $(x,y,min_p,max_p,min_t,max_t)$, storing the cost of the minimum path to node $(x,y)$, such that the minima and maxima since the last checkpoint are $(min_p,max_p,min_t,max_t)$.
Since there are $m+n$ candidate values for each minimum and maximum, this table may be huge, namely size $O(m\cdot n\cdot (m+n)^4)$.
You can implement this using a hash-table, mapping each $(x,y,min_p,max_p,min_t,max_t)$.
// T[x,y,min_p,max_p,min_t,max_t] will eventually contain:
// the minimum cost of a path (excluding the cost since the last checkpoint) to node (x,y)
// such that the minimum P.p or Q.p since the last checkpoint of that path is min_p, etc.
T = empty hash table
for x in [0..m-1]
  for y in [0..n-1]
    for min_p in P.ps + Q.ps
      for max_p in P.ps + Q.ps
        for min_t in P.ts + Q.ts
          for max_t in P.ts + Q.ts
            T[x,y,min_p,max_p,min_t,max_t] = infinity
// there is only one path to (0,0)
// if we don't count the cost since the last checkpoint, this path has cost 0
T[0,0,min(P[0].p,Q[0].p),max(P[0].p,Q[0].p),...] = 0
for x in [0..m-1]
  for y in [0..n-1]
    for min_p in P.ps + Q.ps
      for max_p in P.ps + Q.ps
        for min_t in P.ts + Q.ts
          for max_t in P.ts + Q.ts
            cost_to_xy = T[x,y,min_p,max_p,min_t,max_t]
            // try advance P
            if x
The cost of the optimal path is then the minimum over all
$T[m-1,n-1,min_p,max_p,min_t,max_t] + max_t - min_t + max_p - min_p$
Disclaimer: This solution is not at all optimized and you still have to fill some blanks. Neither does it give you the actual path, but you can get it with some small tweaks.


---

