2

Given a weighted undirected graph, I need to find the shortest path between two nodes, a classical shortest path problem actually. But there is one more constraint : Each node contains a "reduction" value that can be used to reduce the cost of the following edges for one traversal(not only adjacent, and reduction are not cumulative). So you can reduce the cost of an edge using the "Reduction" that was in one of the node you went throught before (the final cost for each edge can't be less than 0).

Note that once we went throught a node with a reduction, we can use it again for all the following edges (not just adjacent, and it is available an unlimited amount of time). Reduction doesn't accumulate.

Let's consider this graph :

enter image description here

in this graph the shortest path from node 1 to 5 is :

  • 1 -> 4 for a cost of 13 (15-2)
  • 4 -> 3 for a cost of 0 (12-12)
  • 3 -> 5 for a cost of 0 (10-12) In this case, we reuse the reduction of node 4 because it is bigger than the reduction of node 3 (We went throught the node n°4 then we have an unlimited amount of reduction of cost 12). It is 0 and not -2 because the weight of an edge can't be negative.

Then the total cost from node 1 to node 5 is 13 + 0 + 0 = 13

To solve this problem, I've tried to use the classical Dijkstra/Bellman-Ford but it didn't work, can you help me with this ?

19
  • 1
    I suggest you show some actual code. The solution will depend on your implementation, your data model, i.e., how your graph looks like in code, etc. Also, be detailed, please. Don't tell us to solve your problem but what you don't understand or what approach you tried and why it failed.
    – cadaniluk
    Feb 17, 2018 at 20:30
  • Ok, the only idea I have is to test all the possible paths from A to B and take the cheaper. But an algorithm like that will never work in time... Then I want to find a better approach and for that I need your help :)
    – Faithe
    Feb 17, 2018 at 20:44
  • I am confused with your example. Do the reductions accumulate? Was the final reduction 12 or 14 when you reached node 5?
    – giusti
    Feb 17, 2018 at 20:55
  • I'm sorry, I think I didn't explain it really well :/. The reduction doesn't accumulate and the final reduction was 12.
    – Faithe
    Feb 17, 2018 at 21:00
  • Ah, ok. So once you've got the reduction of 12 at node 4, you can choose whether to keep it or change for the reduction of 0 at node 3?
    – giusti
    Feb 17, 2018 at 21:06

2 Answers 2

1

It seems to be this can be solved with a variation of Bellman-Ford.

Every path up to a given node can be summarised as a pair (C, D) where C is the cost of that path (after discounts) and D is the best discount factor available on that path. Since a discount can be reused an unlimited number of times once that node has been visited, it makes sense to always use the biggest discount seen so far on that path. For example, the path (1 -> 4 -> 3) has cost C = 13 and discount D = 12.

The complication over the undiscounted problem is that we cannot tell from the cost what the "best" path is to nodes in between the source and destination. In your example the path (1 -> 2 -> 3) has lower cost than (1 -> 4 -> 3), but the latter has a better discount which is why the best path from 1 to 5 is (1 -> 4 -> 3 -> 5).

Rather than recording the lowest cost path to each node (in Bellman-Ford algorithm), we need to record all "feasible" paths from the source to that node found so far. A path can be said to be feasible if there is no other known path that has both a lower cost and a better discount. After the algorithm terminates we can take from all feasible paths from source to destination the one with the smallest cost, ignoring the discount.

(Edit: I originally suggested Djikstra could be used but I think that not be so straightforward. I'm not sure we can choose "the closest" unvisited node in any meaningful way such that we are guaranteed to find the minimal path. Someone else might see how to make it work though...)

1

I think you can use a Dijkstra-type algorithm. Dijkstra's algorithm can be thought of computing the minimum spanning tree that contains the shortest paths from a source vertex to all other vertices. Let's call this the "Dijkstra tree" that contains all the shortest paths from a given source vertex.

Dijkstra keeps adding new vertices to the current tree. For the next vertex he chooses the one that is closest to the current tree. See this animation from wikipedia:

Wikipedia Dijkstra animation

So when Dijkstra adds a new vertex v to an already inserted vertex u (of the current tree), the edge weight of {u, v} has to be considered. In your case, the costs are not just the edge weight of {u, v}, but the weight reduced by the sum of vertex-reductions along the shortest path to u in the current tree. So you have to remember the sum of the vertex reductions along the paths of this "Dijkstra" tree in the vertices.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.