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)$.

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. 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_A$ and the cheapest path from $s_A$ to $t_B$, and take whichever of these is cheaper.

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.

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.