Shortest path from $s$ to $t$ in a graph with $5$ negative edges and no negative cycles?

Question

Let $G=(V,E)$ a directed and weighted ($w:E\to\mathbb{R}$) and let $s,t\in V$. It is given that there are exactly $5$ negative edges and no negative cycles. Find the shortest path from $s$ to $t$.

It seems to me we can still use Dijkstra's algorithm with some modifications. I think this is the intention of this exercise.

It is clear that even without negative cycles, Dijkstra's original algorithm will fail. On the other hand, we have only constant number of negative edges.

I thought about removing those edges or setting their weights to zero, but couldn't think of a proper method to utilize this.

What's the catch?

EDIT
How about running Dijkstra's algorithm on the graph $G$ without any modifications? Then, we look at the "shortest path" from $s$ to $t$ and try to fix it?

Answer 1

Dijkstra's Algorithm in its pure form does not work with negative edge weights. The reason is that it might fix the distance from $s$ to an intermediate node $v$ but finds a shorter path using a negative edge afterwards.

You might consider the following approach to fix this wrong fix:

1. First run Dijkstra's Algorithm in its pure form.
2. Check if the distance label of one of the nodes incident to the edges with negative weights is not yet minimal.
3. If no such node exists then you are done.
4. If there exists such a node $v$ for an edge $(u, v)$ with negative weight then run Dijkstra's Algorithm again with the following modifications:
   • Keep the precomputed distances, but mark all nodes as unvisited.
   • Mark $u$ as visited and start the algorithm at $u$.
5. Go to 2.

The running time of this approach depends on the order in which you consider the nodes whose distance is not yet minimal. If you manage to find the right order of these nodes then you simply run Dijkstra's Algorithm six times. However, if you choose a bad order then you will have to rerun it on the same node several times (up to 32 times if my calculations are correct).

I would try to rerun the algorithm on the node closest to $s$. I cannot give a proof that this is the best order, though. Furthermore, depending on the size of the graph, I would suggest using algorithm which are designed to deal with negative edge weights.