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?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Your final PS is most disturbing: it implies my intuition is totally wrong in solving this problem. (Thanks) $\endgroup$ Commented 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.

Improve this answer
$\endgroup$
1
  • 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$ Commented Nov 30, 2021 at 6:54
0
$\begingroup$

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])
Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.