Single Source Shortest Path Problem with Multiple Weights Each Edge

Question

I am trying to solve the single source shortest path problem, but with the added constraint that there is an additional weight on each edge (so we have two weights in total for each edge, call them p and q) and for this additional weight, we want the shortest path to be strictly monotonically increasing along the whole path (otherwise, for the purposes of this problem, it's not a valid shortest path). So our problem is that we want the shortest path for the value of p and that for every q on each edge in this path, q is increasing.

I am thinking that a solution could build from Bellman-Ford (examining each edge weights) but so far I am stuck, because it seems to me that I need to store information about the paths somehow.

Answer 1

You can use the following variant of the Floyd-Warshall algorithm:

Let $u$ and $v$ be any vertices in the graph. Let $E_u$ and $E_v$ be the set of edges incident on $u$ and $v$, respectively.

Then, define $S[u,v,e_u,e_v,k]$ be the shortest path of at most $k$ edges between $u$ and $v$ that starts at an edge $e_u \in E_u$ and ends at an edge $e_v \in E_v$.

Base Case: $S[u,v,e_u,e_v,1] = w_p(u,v)$ if there exists an edge between $(u,v) = e_u = e_v$; otherwise $S[u,v,e_u,e_v,1] = \infty$.

Dynamic Programming Step: $S[u,v,e_u,e_v,2k] = \min_{w \in V } \Big\{ \min_{e_w, e_w' \in E_w \text{ and } w_q(e_w) < w_q(e_w')} \Big\{ S[u,w,e_u,e_w,k] + S[w,v,e_w',e_v,k] \Big\} \Big\}$.

Final Solution: The value of the shortest path from $s$ to $v$ that satisfies the monotonic constraint is: $\min_{e_s \in E_s, e_v \in E_v} \Big\{ S[s,v,e_s,e_v,|V|] \Big\}$

The running time is polynomial in $|V|$ and $|E|$. It might be an overdo; but it can be a starting point to discover some better algorithm.

Answer 2

Let $G=(V,E)$ be the original graph. Define a new graph, $G'=(V',E')$, that represents the set of all valid paths in $G$, where a path is considered valid if its $q$-values are strictly monotonically increasing.

In particular, $V'=V \times Q$, where $Q=\{q(u,v) \mid u,v \in V\} \cup \{-\infty\}$ is the set of $q$-values that occur on the edges of $G$ along with $-\infty$. Thus, a vertex in the new graph is a pair $\langle v,x \rangle$. Now we have an edge $\langle v,x \rangle \to \langle w,y \rangle$ in the new graph whenever $v \to w$ is an edge in $G$ and $y = q(v,w) > x$, and the $p$-weight on this edge is $p(v,w)$. If $s$ is the source vertex in $G$, then the source vertex in $G'$ is $\langle s,-\infty\rangle$.

Now use any shortest-paths algorithm to find the shortest paths in $G'$ starting from the source $\langle s,-\infty\rangle$. If all $p$-weights are non-negative, you can use Dijkstra's algorithm. If $p$-weights can be negative, use Bellman-Ford.

---

This is a product construction, where you're taking a product between $G$ and a secondary graph which requires that $q$-values be strictly monotonically increasing. See especially How hard is finding the shortest path in a graph matching a given regular language? for the general case, and Shortest path given correct order of colours? and Retrieving the cheapest path of a graph with time-dependent edge weights for a few other analogous examples.