CODEWITHSUNDEEP
algorithmgraph-theorydijkstrareduction
UltimateMath
UltimateMath

Reputation: 95

dijkstra with at most ten negative edges in a path

A question from homework, maybe need to change the implementation of Dijkstra or just reduction somehow.

Let G=(V, E) and let W be a weight function W: E->Z.

All the negative weight edges with the same negative value x. (for example, all the negative weights on edges are with value -10 and all the other are positive)

Let's define "weight up to 10 negative edges," which returns the weight of the path if there is at most ten negative edges or infinity if there are more than ten negative edges.

I need to find a "weight up to 10 negative edges" path from vertex S to all other vertices.

The complexity time should be O(Elog(V)) or O(E+Vlog(V)).

I thought to duplicate the graph ten times and each time there is a negative weight edge we will move from duplicate to the next one. We will make edges with a weight of infinity between the 10th duplicate to the 11th duplicate and run Dijkstra But I don't think it works.

There should be a solution that uses Dijkstra in some way.

Upvotes: 2

Views: 292

Answers (2)

kaya3
kaya3

Reputation: 51043

Dijkstra's algorithm doesn't work with negative edges because it iteratively selects the "unconfirmed" node with the lowest path length, marks it as "confirmed", and then never updates the path length for that node again. If a negative edge exists, then a "shorter" path might be found to a node after it has already been "confirmed", but if the node becomes "unconfirmed" again as a result of that then there could potentially be an infinite loop; the same node could keep getting confirmed then unconfirmed over and over, and the algorithm would never terminate. Any change to the algorithm to solve this problem must address that problem.

As a way to guarantee termination, instead of just recording the path length, you can record a pair like (path length, # of negative edges). When a shorter path to a "confirmed" node is found using a negative edge, the path length may get shorter but the number of negative edges in that path is increased. So you can write a condition to stop updating it if the number of negative edges in the resulting path would be greater than 10.

The problem is more subtle than that, though, because it's no longer the case that the "shortest path so far" to a node is the best one to keep. Suppose you have are looking for a shortest path from A to C using at most 10 negative edges, and you have found a path of length 10 from A to B using no negative edges, and another one from A to B of length 5 using three negative edges; you don't yet know which one leads to a better solution (or a solution at all), because there may be 8 negative edges in the path from B to C. So at each node you need to record not just the pair of (path length, # of negative edges), you need to record a set of all best such pairs.

Hopefully that gives you an idea of how Dijkstra's algorithm can be adapted to solve your problem; there are some remaining details you will need to fill in yourself.

Upvotes: 1

highfructose
highfructose

Reputation: 41

You can't use Dijkstra's algorithm with negative weights and come up with a correct solution. See this other post for the reasoning behind why it fails.

Upvotes: 0

Related Questions