Finding fastest path at additional condition

Question

I'm wondering, if Dijkstra's algorithm will work properly when there is more than one direct connection in an undirected graph.

E.g.:

I want to use Dijkstra to find the fastest path but, there's an additional condition. Sum of all additional_data on the edges can't be >= x. So, if it came out that edge with weight: 3 was wrong to use, my program would try with the 2nd edge.

edit: My task is to find the fastest path, under the additional condition that the sum of additional_data from the edges can not be higher than x. Could you tell me how to handle this problem?

edit2: (setting up on a bounty)

I've been researching internet alot untill I've found this link. There's an explanation of how to do the thing I'm asking for. (Upper-Intermediate acapite)

I'm trying to use it somehow for 2 days now but I'm worried I do not understand this algorithm correctly. I'd like to ask some of you to help me with this problem, by explaining me a little more on example (few first steps). Here's the example:

Answer 1

This problem is NP-complete. No algorithm is more efficient than the one explained by multiple people (Tom Anderson, user1884905).

Proof: By reducing of subset-sum for non-negative numbers.

Take an instance A of subset-sum (N numbers). Construct a graph, where there are N+1 nodes. For nodes i and i+1 , make 2 paths , one with weight=0, additional_data=A[i], another with weight=A[i], additional_data=0. Choose x(the limit for sum of additional_data).

Observe that the algorithm must minimize sum of weights, so it will also maximize sum of additional_data. So the paths of the first kind chosen will be the paths associated with numbers in the result of the subset-sum problem.

Answer 2

you can use the bellman-ford algorithm with the assumption that your addittional-data is the number of edges parameter in the bellman-ford algorithm.

Answer 3

The additional condition will break Dijkstra. Think of it like this: if you have a path A->B in a graph and an edge B->C in a graph, then the shortest path A->C that involves B is surely the minimum path of A->B->C. In your case this condition doesn't hold, because while A->B and B->C might be valid, A->B->C might not be valid.

Okay, this is the point where you grab a piece of paper and try this.

If you look at your graph, and assuming you want to go from (1) to (4), notice how you can eliminate (3) by introducing the following edges:

• (1)->(4), [390, 2]
• (1)->(2), [383, 3]
• (2)->(4), [391, 3]

Once you have eliminated the all edges but a straight line, the problem becomes somewhat easier: for each node you can keep track of how much [distance, additional] it will cost to reach the goal. You don't have to store additional > max or 'remaining additional' < 0, since that's not a viable solution. Also, if you have multiple distances for equal additional, only the minimal distance should be kept.

The best solution is now the one with the minimal distance in the last node (or the first, depending on how you ordered it). If down the road, you kept pointers on how you got there (e.g. if you update the value in the matrix also store the element that made it change), you can backtrack the path as well.

Here you should note that you can do the same when the problem was in the non-eliminated form with the matrix you suggest: x-axis as nodes, y-axis as 'list per node'.

That should do it.

Answer 4

I think you can modify Dijkstra's algorithm to handle this. Dijkstra's algorithm basically works by incrementally building a table listing the shortest path to every node. You would instead build a table listing the shortest path to every node at a given cost. Or rather, at a given cost or less, ie on a given budget.

More formally, you can transform your original graph into another graph, and then apply Dijkstra to that graph. Assuming that the additional_data cost is always an integer, the transformation is:

1. Take every original node n and create a set of nodes (n, c) for every integer value of c from 0 up to the value of the budget (the maximum sum of additional_data that you can tolerate)
2. Take every original connection n1 -> n2 with weight w and additional_data a, and create a set of connections from every node (n1, c) to the node (n2, c+a), each with weight w

The nodes in the original graph model positions in space. The nodes in the transformed graph model positions in a state space, where the state variables are position, and the amount of the budget spent so far.

If you want to get from A to Z with a budget of x, then you then simply use Dijkstra's algorithm to find a route from (A, 0) to one of the nodes (Z, c <= x).

EDIT: I have implemented the modified Dijkstra's algorithm: https://bitbucket.org/twic/roadsproblem. The crux of it is in src/solver.py.

Answer 5

Here is an explanation of how the algorithm you have found will handle your example problem.

The problem is to find the shortest path between node one and node four with the extra condition that the accumulated cost along the way should not be more than 7.

The solution we want to find is to first go from node one to node node two, a distance of 190 and at a cost of 4. And then go from node two to node four using the path of distance 195 and cost 3. In total the path has a distance of 385and a cost of 7.

Step 1

So how does the algorithm find this? The first step is to set up the matrix minArray(i,j) just like you have done. The element (i,j) of the array holds the distance you must travel to get to node j with exactly i money remaining.

Starting out there are no visited elements and since we are starting at node one with 7 "monies" the top left element is set to zero. The empty spaces in the table above correspond to values that are set to infinity in the array.

Step 2

Next, we find the lowest value of the array, this is the zero at position (remaining money, node) = (7,1). This element is set to visited (the state of an element is kept track of using a matrix visitedArray of the same size as minArray) which means that we have selected node one. Now all nodes that connect to node one are updated with values by traversing the corresponding edges.

Here minArray(6,3) = 191 which means that we have gone a distance of 191 to get to node three and the money we have left is 6 since we have payed a cost of 1 to get there. In the same way minArray(3,2) is set to 190. The red square marks that element (7,1) is visited.

Step 3

Now we again find the lowest unvisited element (which is minArray(3,2) = 190), set it to visited and update all elements that connect to it. This means that the distance is accumulated and the remaining money is calculated by subtracting the cost from the current value.

Note that it is too expensive to go back to node one from node two.

Step 4

The next step, selecting minArray(6,3) = 191 looks like this.

Step 5

Three steps later the array looks like this. Here the two elements that equal 382 and the one that equals 383 have been selected. Note that the value of an element is only updated if it is an improvement of (i.e. lower than) the current value.

Step 6

The array continues to fill up until all elements are either visited or still have infinite value.

Final step

The final step is to find the total distance by finding the lowest value of column four. We can see that the minimal value, minArray(0,4) = 385 corresponds to the correct solution.

Note: If all values of column four would have been infinite, it would mean that there is no valid solution. The algorithm also specifies that if there are multiple values of equal and minimal distance in column four, the cheapest one is selected.

Answer 6

You could make a copy of the node with 0 cost between them that adds the 2nd possible path.

Like so (pseudocode)

Node 1____
|         |
|path1    |
|cost=3   |path2 cost=5
|         |
Node 2____/

becomes this:

Node 1____cost=0____Node 1a
|         path 1a     |
|path1                |path2
|cost=3               |cost=5
|                     |
Node 2________________/

Not sure if this will work, but it's an idea.

Answer 7

I do not think Dijkstra's algorithm is a good solution to this problem since the distance needed is not only the source node and destination. Here is a solution based upon A* search algorithm.\

First, perform a FolydWarshall based on weight and then based on additional_data to get the least weight and least additional_data for each node pair in the graph.

  FloydWarshall(Weights);
  FloydWarshall(Additional_datas);

Second, we perform a A* search based on priority queue with element like following structure(Use c code as example.) The priority queue will automatically get the weights_sum least in all the candidates. weights_expected is the best guess of the path through current node to destination node while weights_now is current weight

  struct NODE
    {
        int node;
        int weights_expected;
            int weights_now;
        int additional_datas_now;
            bool visited;
    };
    bool operator < (const NODE &A,const NODE &B)
    {
        return A.weights_expected>B.weights_expected || (A.weights_expected==B.weights_expected && 
   A.additional_datas_now>B.additional_datas_now);
    }

In A* search algorithm,

1) we first put the source node into priority queue. 
  2) while Priority Queue is not empty:
        Set **A** equal to the head of priority queue and pop out the head of priority queue. 
        A.visited=True;
        if A is the destination node **Dest**, **return** A.weights_expected. 
        For each neighbors **B** of node **A**, 
          if A.visited==False **and** A.additional_datas_sum+|AB|.additional_data+Additional_datas[B][Dest]<=x, 
               1) B.additional_datas_now=A.additional_datas_now+|AB|.additional_data;    
               2) B.weights_now=A.weights_now+|AB|.weight;
               3) B.weights_expected=B.weights_now+Weights[B][Dest];
               3) push node B into priority Queue. 
   3) Print "Do not find a proper path" //if code came to here, that means the if in 2) do not return a value. 

A* search will be still NP hard since in worst case it has to search each possible path. However it will be much faster than a simple DFS search and perform lots of search path cuts.

Answer 8

Your additional condition makes the problem a lot harder. Looking at it, I think the only thing you can do, is find out all possible paths between the source and the target, sort them by total edge weight, and then check one by one if your additional condition holds.

However, the problem of finding all possible paths between two vertices, is NP-Hard. A slightly modified version of DFS might be able to do the trick, but probably not in all cases.