10
$\begingroup$

Given a directed graph $G = \langle V,E \rangle$ with $n$ vertices and $m$ edges and a weight function $w:E \rightarrow \mathbb{R}$, together with two vertices $s$ and $t$ in $V$:

Describe an efficient algorithm that finds the "cheapest" (in terms of $w$) path from $s$ to $t$ that uses at most one negative edge, or returns that there is no such path.

I was thinking about building a new graph $G'$ which will be equal to $G$ after we removed all of the negative edges from it.

$G'$ contains only non-negative edges, hence we can run Dijkstra on it. Let $s_0$ be the weight of the path we found from $s$ to $t$, if we didn't find a path we will set $s_0=\infty$.

Let $e_1,...,e_k$ be the negative value edges that we removed from $G$, $\forall i: 1\le i\le k:$

  1. we can run a modified version of Dijkstra on $G' \cup \{e_i\}$ (when there is only one negative valued edge in a graph we can modify Dijkstra and it will still work in $O(m+n \log n)$.
  2. Let $s_i$ be the weight of the path we found in the $i$-th Dijkstra run. (Again if there is no path we will set $s_i=\infty$).
  3. If $\min\{s_0,...,s_k\}<\infty$ we return it, otherwise we retrun that there is no such path.

This algorithm runs in $O(m \cdot (m+n \log n))$ since in the worst case we will run Dijkstra $O(m)$ times.

Is there any way to optimize this algorithm, or is there a way to make the problem easier to solve with a better algorithm?

$\endgroup$
0

2 Answers 2

11
$\begingroup$

You can use Dijkstra twice to find in your $G'$ the cost for each vertex $v \in V$, the cost of the optimal $s$-$v$-path and the cost of the optimal $v$-$t$-path. Store this in a table creatively called OPT.

Now, for each negative edge $e=(u,v)$ in $e_1, e_2, ..., e_k$, the cost of the optimal $s$-$t$-path allowing $e$ is $$\text{OPT}^+(s,t,e) = \min \begin{cases} \text{dist}(s,t) \\ \text{OPT}(s,u) + w(e) + \text{OPT}(v,t) \end{cases}$$

Running time is that of Dijkstra's.

Output $\min_{i \leq k}\text{OPT}^+(s,t,e_i)$.


Ps, if by path you mean simple path, then the problem is NP-hard by a reduction from the classic 2-Disjoint Paths problem.

$\endgroup$
1
  • 2
    $\begingroup$ Your final PS is most disturbing: it implies my intuition is totally wrong in solving this problem. (Thanks) $\endgroup$ Nov 29, 2021 at 15:24
11
$\begingroup$

Another approach is to create a single graph $H$ as follows:

  • each vertex in $G$ has two counterparts in $H$: vertex $s$ becomes $s_A$ and $s_B$, vertex $t$ becomes $t_A$ and $t_B$, and so on.
  • each nonnegative-weight edge in $G$ has two counterparts in $H$, namely, edge $(u, v)$ becomes $(u_A, v_A)$ and $(u_B, v_B)$.
  • but each negative-weight edge in $G$ has only one counterpart in $H$, namely, edge $(u, v)$ becomes $(u_A, v_B)$. Additionally, we increase the weights of these counterparts, all by the same amount, to make them all nonnegative (so that $H$ has only nonnegative-weight edges — necessary for Dijkstra).
  • and there is one extra edge from $t_A$ to $t_B$, whose weight is the amount by which we increased the weights of the negative-weight edges. (That is: we add a zero-weight edge from $t_A$ to $t_B$, then increase its weight the same as we did the negative-weight edges.)

So $H$ essentially has two copies of $G$, where nonnegative-weight edges are within a copy and negative-weight edges carry from copy $A$ to copy $B$ — but never back — plus one extra "free" edge from copy $A$ to $B$. As a result, any path within $H$ corresponds to a path within $G$ that uses at most one negative-weight edge.

You can then run Dijkstra's algorithm on $H$ to find the cheapest path from $s_A$ to $t_B$. (Note: to obtain its cost, subtract the extra weight that we added to each of the negative-weight edges.)

This has the same asymptotic complexity as the approach that Pål GD describes. It can also easily be extended to a problem where we want a path with at most two negative-weight edges (using three copies of $G$), at most three (using four copies), etc., with the caveat that this will allow the same negative-weight edge to be reused each time.

$\endgroup$
2
  • 2
    $\begingroup$ Dijkstra's algorithm doesn't support a graph with negative-weight edges. This issue can be fixed by adding $\max -w_{u,v}$ to all negative-weight edges, so all edges have nonnegative weights. $\endgroup$
    – pcpthm
    Nov 30, 2021 at 6:54
  • $\begingroup$ @pcpthm: Whoops, good call -- will fix; thanks! $\endgroup$
    – ruakh
    Nov 30, 2021 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.