Find shortest path between two vertices that uses at most one negative edge

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?

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.

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

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.

• 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. Nov 30, 2021 at 6:54
• @pcpthm: Whoops, good call -- will fix; thanks! Nov 30, 2021 at 7:07