0

In this scenario, the aim is to find a path with the smallest total weight. There are 5 sections with each section having different nodes. The nodes are only connected to nodes in adjacent sections and a path must consist of only a single node from each section.

For example, let:

  • section 1 has nodes [1, 2, 3].
  • section 2 has nodes [4, 5].
  • section 3 has nodes [6].
  • section 4 has nodes [7, 8, 9, 10, 11].
  • section 5 has nodes [12, 13, 14].

A valid path through the sections is [1, 4, 6, 7 , 12] and also [1, 5, 6, 11, 14] etc...

All nodes have negative weights but negative cycles are impossible (due to the one node per section policy). Therefore, does the process of adding a constant to each node resolve the issue of negative weights? If it can fix the issue, are there any papers which show this? I know there are other algorithms to resolve negative weights but I'm interestted in Dijkstra's algorithm. Thanks.

Improve this question
4
  • 1
    Sure, adding a constant fixes the problem in this case, but in an acyclic graph there are faster and simpler ways, like DFS. Commented May 23, 2021 at 16:40
  • @MattTimmermans I second that. Dijkstra is just an incredibly poor choice for this problem. You don't have to think about Bellman-Ford. You just relax edges from left to right in O(n+m) and you're done. I don't understand how DFS could help, though. Commented May 25, 2021 at 9:00
  • Relax edges from left to right? Sorry I don't understand. Commented May 25, 2021 at 14:04
  • "Edge relaxation" refers to the process of checking whether a node's total distance (from the source) can be reduced by adding an edge's length to the distance of the start. Since you have weights for nodes (not vertices), the easiest way is as follows: Assign all nodes in section one their weight as distance. Then proceed with section two. For every node, calculate the minimum distance of a connected node in section one and add the node's weight. That is the minimum path cost to each section two node. Repeat the same for the following levels. In level 5, pick the minimum. Commented May 26, 2021 at 17:28

1 Answer 1

Reset to default
3

No, you can't do this. Let's have a look at the counter example. Suppose we have a graph with A, B, C nodes and egdes:

A - B  -2 (negative)
A - C   6
B - C   7

we are looking for the shortest path from A to C. In the original graph we have

A - B - C  => -2 + 7 = 5 (the shortest path, 5 < 6)
A - C      => 6

The best choice is A - B - C. Now, let's get rid of negative edges by adding 2. We'll have now

A - B  0 
A - C  8
B - C  9

A - B - C  => 0 + 9 = 9
A - C      => 8         (the shortest path, 8 < 9)

Please note, that now the shortest path is A - C. Alas! While adding constant value to each edge we ruin the problem itself; and it doesn't matter now which algorithm we use.

Edit: Counter example with all edges (arc to prevent negative loops) being negative:

A -> B -6
B -> C -1
A -> C -5

Before adding 6 we have

A -> B -> C = -6 - 1 = -7 (the shortest path)
A -> C      = -5

After adding 6 we get

A -> B  0
B -> C  5
A -> C  1

A -> B -> C = 0 + 5 = 5 
A -> C      = 1 (the shortest path)
Improve this answer
Sign up to request clarification or add additional context in comments.

13 Comments

Makes sense. However, all weights are strictly negative. Does it work in this case?
@hi hi: You can't add constant value to edges; all negative weights is not the exception (please, see my edit)
Good answer. Is the Bellman–Ford algorithm the best algorithm to use in this case then?
@hi hi: Bellman-Ford is quite easy to implement and it provides the right answer. As for the best you should specify the criterium; for instance, in case of huge graph A* search can be preferrable.
there are 12 sections - each having around 30 nodes. Isn't A* just Dijkstra with a heuristic meaning it wouldn't work in this case? I need the optimal path.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.