Single Source Shortest Path Problem with Multiple Weights Each Edge

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.

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.

StackExchange Computer Science Q#160670, answer score: 2