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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

This is a more general algorithm that computes the distance that uses at most one negative edge for all vertices.

def LikeBellmanFord(s):
    dpos[s] = 0
    dneg[s] = float('inf')

    for v in vertices:
        if v != s:
            dpos[v] = float('inf')
            dneg[v] = float('inf')

    for i in range(1, len(vertices)):
        for (x, y) in edges:
            if w(x, y) > 0:
                dpos[y] = min(dpos[y], dpos[x] + w(x, y))
                dneg[y] = min(dneg[y], dneg[x] + w(x, y))
            elif w(x, y) < 0:
                dpos[y] = dpos[y]
                dneg[y] = min(dneg[y], dpos[x] + w(x, y))

    # Check for negative cycles
    for (u, v) in edges:
        if d[v] > d[u] + w(u, v):
            print("Negative Circle")

    # Calculate final distances
    for v in vertices:
        if v != s:
            d[v] = min(dpos[v], dneg[v])