3
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ I think Dijkstra's algorithm still works when the directed graph doesn't have negative cycles. If that is not the case, that is, there is at least one negative cycle, then Bellman-Ford algorithm might be what you're looking for. I don't know of any easier way, but I'm not expert, so take it with a grain of salt. $\endgroup$
    – user313212
    Jul 4, 2016 at 10:48
  • 1
    $\begingroup$ Obviously I could use Bellman-Ford algorithm, but the solution should be as efficient as possible $\endgroup$
    – LiorGolan
    Jul 4, 2016 at 10:55
  • $\begingroup$ I'm almost certain that if no negative weight cycles exist (which Bellman-Ford would also fail at) there is a way to re-weight the edges so that all are positive. $\endgroup$
    – Jared
    Jul 5, 2016 at 8:39
  • 1
    $\begingroup$ @Jared: I think your approach is incorrect. Consider the graph with two paths from the source $s$ to the sink $t$: the first is a unique edge $s-t$ with cost $1$, the second is the chain $s-v-t$, with costs $c_{sv}=-2$ and $c_{vt}=2$ (i.e., total cost $0$). With your approach the modified graph would give the first path cost $1+2=3$, and the second path cost $(-2+2)+(2+2)=4$. This is obviously incorrect, as the shortest path is $s-v-t$. $\endgroup$
    – Kuifje
    Jul 5, 2016 at 15:25
  • 1
    $\begingroup$ @Jared: Johnson's algorithm provides such a re-weighting scheme, but it requires using Bellman Ford's algorithm to compute the new costs. There is probably a more efficient way than computing Bellman Ford, and then Dijkstra on the new graph, but the approach is still interesting. $\endgroup$
    – Kuifje
    Jul 6, 2016 at 15:30

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .