# #StackBounty: #algorithms #graphs #shortest-path #weighted-graphs #dag Shortest Path in a Directed Acyclic Graph with two types of costs

### Bounty: 50

I am given a directed acyclic graph $$G = (V,E)$$, which can be assumed to be topologically ordered (if needed). The edges in G have two types of costs – a nominal cost $$w(e)$$ and a spiked cost $$p(e)$$.

The goal is to find a path from a node $$s$$ to a node $$t$$ that minimizes the following cost: $$sum_e w(e) + max_e {p(e)},$$ where the sum and maximum are taken over all edges of the path.

Standard dynamic programming methods show that this problem is solvable in $$O(E^2)$$ time. Is there a more efficient way to solve it? Ideally, an $$O(Ecdot operatorname{polylog}(E,V))$$ algorithm would be nice.

—- EDIT —–

This is the $$O(E^2)$$ solution I found using dynamic programming, if it’ll help.

First, order all costs $$p(e)$$ in an ascending order. This takes $$O(Elog(E))$$ time.

Second, define the state space consisting of states $$(x,i)$$ where $$x$$ is a node in the graph and $$iin {1,2,…,|E|}$$. It represents "We are in node $$x$$, and the highest edge weight $$p(e)$$ we have seen so far is the $$i$$-th largest".

Let $$V(x,i)$$ be the length of the shortest path (in the classical sense) from $$s$$ to $$x$$, where the highest $$p(e)$$ encountered was the $$i$$-th largest. It’s easy to compute $$V(x,i)$$ given $$V(y,j)$$ for any predecessor $$y$$ of $$x$$ and any $$j in {1,…,|E|}$$ (there are two cases to consider – the edge $$yto x$$ is has the $$j$$-th largest weight, or it does not).

At every state $$(x,i)$$, this computation finds the minimum of about $$deg(x)$$ values. Thus the complexity is $$O(E) cdot sum_{xin V} deg(x) = O(E^2)$$, as each node is associated to $$|E|$$ different states.

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.