<ol>
<li>There exists an optimal solution $p,q,c$ such that $c_e = l_e$ for all edges $e$ in the path $q$ and $c_e = u_e$ otherwise.</li>
<li>For the optimal solution from point 1 exists a vertex $x$ at which the paths $p$ and $q$ split. The subpath $p^x$ of $p$ from $x$ to $v$ is a shortest path from $x$ to $v$ for the edge weights $u$ (the upper bound).  </li>
</ol>

<p>To solve the problem consider the following procedure:</p>

<p>For all $x \in V$:</p>

<ul>
<li>Compute the length of the shortest path from any vertex $y \in V$ to $w$ for the edge weights $u$. The lengths are stored in $d \in \mathbb{N}^V$.</li>
<li>Define the node potentials $\pi_y = d_x - d_y$.</li>
<li>Compute the shortest path from $x$ to $v$ that respects the node potentials $\pi$, i.e. choose the edge weights such that the shortest path to $v$ with respect to $c$ is greater or equal to $\pi_y$ for all $y \in V$. This can be done by a modified Dijkstra algorithm. The Dijkstra algorithm normally takes fixed edge weights $c$. We choose the edge weights as follows: $\min\{ c \in [l_e,u_e] \mid \pi_w \leq d(u) + c \}$. Furthermore, make sure to take the shortest path that only uses edges with edge weights at their lower bound if possible.</li>
<li>If the above procedure finds a shortest path from $x$ to $v$ that only uses edges with edge weights at their lower bound, then $x$ might be a splitting point from point 2. Remember that $x$ as well as the resulting edge costs $c^x$</li>
</ul>

<p>For all the remembered pairs of vertices $x$ and corresponding edge costs $c^x$, compute the shortest path to $x$, simillar to the shortest path from $x$ to $v$. Now change $c_e^x$ to $l_e$ for all edges in that shortest path. The solution to problem is now given by
$$ \max_{x}\{c_p^x - c_q^x \mid p \text{ is a shortest } s,w \text{-path}, q \text{ is a shortest } s,v \text{-path} \}. ~~~~~~~ (1)$$ </p>

<p>Illustration of correctness:</p>

<p>Let $\mathcal{D}$ be the domain of the original problem and $p,q,c^x$ the solution of (1), then we have $(p,q,c^x) \in \mathcal{D}$. Hence, the solution of (1) is smaller or equal to the solution of the original problem.</p>

<p>Now let $(p,q,c)$ be the solution of the original problem and let $x$ be the splitting point of the two paths $p$ and $q$. The described procedure considers $x$ and computes the shortest path to $v$, which is exactly $p(x \rightarrow v)$, such that the shortest path $\rho$ to $w$ is the shortest path with respect to the edge weights at their upper bound $u$. We therefore get:
$$ c_p - c_q = c_{p(s \rightarrow x)}  + c_{p(x \rightarrow w)} -  c_{q(s \rightarrow x)}  + c_{q(x \rightarrow v)} \\
= c_{p(x \rightarrow w)} - c_{q(x \rightarrow v)} \leq c_{p(x \rightarrow w)} - c_{\gamma}. $$
Hence, the solution of (1) is greater or equal to the solution of the original problem.</p>

<p>To prove the correctness of the modified Dijkstra algorithm, one can modify the original proof.</p>

CC BY-SA 3.0
2018-01-15T17:25:20.983Z
Looks promising.  Can you explain why you think your algorithm is correct?
Neal Young
CC BY-SA 4.0
2021-09-10T18:46:06.163Z
A solution to the problem is published here: https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/8271
Florian K
CC BY-SA 3.0
2018-01-11T16:13:05.487Z
2018-01-25T11:39:23.690Z
2018-01-25T11:39:23.690Z
Florian K
<p>My problem is the following maximization problem:</p>

<p>Given: A graph $G=(V,E)$, lower bounds $l \in \{0,1,..,K\}^E$ and upper bound $u \in \{0,1,..,K\}^E$ for the edge weights, a source $s$ and two targets $v$ and $w$.</p>

<p>Problem: Compute 
$$ \max\{ c_p - c_q | p \text{ is a shortest } s,w \text{-path}, q \text{ is a shortest } s,v \text{-path}, c \in [l,u] \} $$ 
with $c_p$ and $c_q$ being the costs of path $p$ and $q$, respectivly.</p>

<p>I cannot image that that this problem has not been studied, but i cannot find anything. Does someone know the name of this problem and any resources.</p>

<p>Thanks in advance.</p>

<p>The problem can also be formulated as the following bilevel program:</p>

<p>$$ \max ~~~~~~~~~~~~~ c^Tx - c^Ty ~~~~~~~~~~~~~~~~~~~\\
s.t. x \in \arg\min \{ c^Tx| Mx=b^{s,w} \}, \\
~~~~~~~  y \in \arg\min\{ c^Ty | My=b^{s,v} \},  \\
 l \leq c \leq u  $$</p>

<p>with $M$ being the vertex-edge incidence matrix of the graph and $b^{s,v},b^{s,w} \in \{0,1\}^V$ defined as follows: , $b_s^{s,v} = b_s^{s,w} = 1$, $b_v^{s,v} = b_w^{s,w} = -1$, and $0$ otherwise.</p>

CC BY-SA 3.0
2017-12-21T15:52:14.263Z
Are $p$ and $q$ shortest paths?
Sasho Nikolov
CC BY-SA 3.0
2017-12-21T16:21:38.880Z
yes, I am looking for the maximal possible cost difference between two shortest paths
Florian K
CC BY-SA 3.0
2017-12-31T04:24:52.453Z
What is the role of the upper and lower bounds?  What weights do you use to determine the costs of the two paths?  Oh, I see: you are saying to choose each edge weight $c_e$ (subject to the upper and lower bounds) so as to maximize the resulting difference $dist_c(s, w) - dist_c(s, v)$.
Neal Young
CC BY-SA 3.0
2017-12-31T15:13:11.403Z
Correct. Basically, the edge weights are uncertain but inside a known interval. The maximization finds a worst case scenario under which the path to $w$ is maximal more expansive then to $v$.
Florian K
CC BY-SA 3.0
2017-12-31T15:22:00.097Z
I’m pretty sure that the problem can be solved in polynomial time. I will post a solution when I have it in a proper format.
Florian K
CC BY-SA 3.0
2018-01-02T18:31:07.177Z
Is the graph $G$ directed?
Neal Young
CC BY-SA 3.0
2018-01-02T18:32:38.583Z
Yes. It is a directed graph.
Florian K
CC BY-SA 3.0
2018-01-05T14:31:25.463Z
Am interested to see your poly-time algorithm.  My first guess would be that this problem is NP-hard.
Neal Young
<graph-algorithms><optimization><shortest-path>
Maximum difference between two shortest paths
Florian K
# Maximum difference between two shortest paths

(Asked by: username_0 on 2017-12-21)

My problem is the following maximization problem:

Given: A graph $G=(V,E)$, lower bounds $l \in \{0,1,..,K\}^E$ and upper bound $u \in \{0,1,..,K\}^E$ for the edge weights, a source $s$ and two targets $v$ and $w$.

Problem: Compute
$$ \max\{ c\_p - c\_q | p \text{ is a shortest } s,w \text{-path}, q \text{ is a shortest } s,v \text{-path}, c \in [l,u] \} $$
with $c\_p$ and $c\_q$ being the costs of path $p$ and $q$, respectivly.

I cannot image that that this problem has not been studied, but i cannot find anything. Does someone know the name of this problem and any resources.

Thanks in advance.

The problem can also be formulated as the following bilevel program:

$$ \max ~~~~~~~~~~~~~ c^Tx - c^Ty ~~~~~~~~~~~~~~~~~~~\\
s.t. x \in \arg\min \{ c^Tx| Mx=b^{s,w} \}, \\
~~~~~~~ y \in \arg\min\{ c^Ty | My=b^{s,v} \}, \\
l \leq c \leq u $$

with $M$ being the vertex-edge incidence matrix of the graph and $b^{s,v},b^{s,w} \in \{0,1\}^V$ defined as follows: , $b\_s^{s,v} = b\_s^{s,w} = 1$, $b\_v^{s,v} = b\_w^{s,w} = -1$, and $0$ otherwise.

**Tags:** graph-algorithms, optimization, shortest-path
> **Comments:**
> **username_1**: Are $p$ and $q$ shortest paths?  
> **username_0**: yes, I am looking for the maximal possible cost difference between two shortest paths  
> **username_2**: What is the role of the upper and lower bounds?  What weights do you use to determine the costs of the two paths?  Oh, I see: you are saying to choose each edge weight $c_e$ (subject to the upper and lower bounds) so as to maximize the resulting difference $dist_c(s, w) - dist_c(s, v)$.  
> **username_0**: Correct. Basically, the edge weights are uncertain but inside a known interval. The maximization finds a worst case scenario under which the path to $w$ is maximal more expansive then to $v$.  
> **username_0**: I’m pretty sure that the problem can be solved in polynomial time. I will post a solution when I have it in a proper format.  
> **username_2**: Is the graph $G$ directed?  
> **username_0**: Yes. It is a directed graph.  
> **username_2**: Am interested to see your poly-time algorithm.  My first guess would be that this problem is NP-hard.  

---

## 1 answers

### Answer by username_0 on 2018-01-11. Score: 1 | Accepted answer

1. There exists an optimal solution $p,q,c$ such that $c\_e = l\_e$ for all edges $e$ in the path $q$ and $c\_e = u\_e$ otherwise.
2. For the optimal solution from point 1 exists a vertex $x$ at which the paths $p$ and $q$ split. The subpath $p^x$ of $p$ from $x$ to $v$ is a shortest path from $x$ to $v$ for the edge weights $u$ (the upper bound).

To solve the problem consider the following procedure:

For all $x \in V$:

* Compute the length of the shortest path from any vertex $y \in V$ to $w$ for the edge weights $u$. The lengths are stored in $d \in \mathbb{N}^V$.
* Define the node potentials $\pi\_y = d\_x - d\_y$.
* Compute the shortest path from $x$ to $v$ that respects the node potentials $\pi$, i.e. choose the edge weights such that the shortest path to $v$ with respect to $c$ is greater or equal to $\pi\_y$ for all $y \in V$. This can be done by a modified Dijkstra algorithm. The Dijkstra algorithm normally takes fixed edge weights $c$. We choose the edge weights as follows: $\min\{ c \in [l\_e,u\_e] \mid \pi\_w \leq d(u) + c \}$. Furthermore, make sure to take the shortest path that only uses edges with edge weights at their lower bound if possible.
* If the above procedure finds a shortest path from $x$ to $v$ that only uses edges with edge weights at their lower bound, then $x$ might be a splitting point from point 2. Remember that $x$ as well as the resulting edge costs $c^x$

For all the remembered pairs of vertices $x$ and corresponding edge costs $c^x$, compute the shortest path to $x$, simillar to the shortest path from $x$ to $v$. Now change $c\_e^x$ to $l\_e$ for all edges in that shortest path. The solution to problem is now given by
$$ \max\_{x}\{c\_p^x - c\_q^x \mid p \text{ is a shortest } s,w \text{-path}, q \text{ is a shortest } s,v \text{-path} \}. ~~~~~~~ (1)$$

Illustration of correctness:

Let $\mathcal{D}$ be the domain of the original problem and $p,q,c^x$ the solution of (1), then we have $(p,q,c^x) \in \mathcal{D}$. Hence, the solution of (1) is smaller or equal to the solution of the original problem.

Now let $(p,q,c)$ be the solution of the original problem and let $x$ be the splitting point of the two paths $p$ and $q$. The described procedure considers $x$ and computes the shortest path to $v$, which is exactly $p(x \rightarrow v)$, such that the shortest path $\rho$ to $w$ is the shortest path with respect to the edge weights at their upper bound $u$. We therefore get:
$$ c\_p - c\_q = c\_{p(s \rightarrow x)} + c\_{p(x \rightarrow w)} - c\_{q(s \rightarrow x)} + c\_{q(x \rightarrow v)} \\
= c\_{p(x \rightarrow w)} - c\_{q(x \rightarrow v)} \leq c\_{p(x \rightarrow w)} - c\_{\gamma}. $$
Hence, the solution of (1) is greater or equal to the solution of the original problem.

To prove the correctness of the modified Dijkstra algorithm, one can modify the original proof.

> **Comments:**
> **username_2**: Looks promising.  Can you explain why you think your algorithm is correct?  
> **username_0**: A solution to the problem is published here: https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/8271  

---

