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:$

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

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

• If $\min\{s_0,...,s_k\}

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.

StackExchange Computer Science Q#146216, answer score: 11