# Shortest Path in a Directed Acyclic Graph with two types of costs

I am given a directed acyclic graph $$G = (V,E)$$, which can be assumed to be topologically ordered (if needed). Each edge $$e$$ in G has two types of costs – a nominal cost $$w(e)$$ and a spiked cost $$p(e)$$. I am also given two nodes in $$G$$, node $$s$$ and node $$t$$.

The goal is to find a path from $$s$$ to $$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(E\cdot \operatorname{polylog}(E,V))$$ algorithm would be nice.

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(E\log(E))$$ time.

Second, define the state space consisting of states $$(x,i)$$ where $$x$$ is a node in the graph and $$i\in \{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 $$y\to 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_{x\in V} \deg(x) = O(E^2),$$ as each node is associated to $$|E|$$ different states.