I am trying to find an efficient solution to my problem. Let's assume that I have positive weighted graph G
containing 100 nodes(each node is numbered) and it is an acyclic graph. So there cannot be any edge like 2,2 or 2,1. I have got a list of nodes let's say 10 from graph G
. Let's say each of these nodes are also in an array. I am looking for a way to find the shortest path's total weight from node 1 to 100 that passes through at least some particular(let's say 5) of those nodes from that list.
To simplify it, consider graph with 6 nodes, 0...5, now node 1 and 4 are marked as points where we could specify to pass. Let's say existing paths are 0-1-2-5, 0-3-4-5, and 1-4. Now let's say all edges are weighted as 5 except 3 to 4 is weighted as 1. If we run a shortest path algorithm this would basically find the path 0-3-4-5 as it is weighted 11. However if we run an algorithm specifying minimum amount of specified points and try the amount 2. Then the algorithm should be running on 0-1-4-5 which is weighted as 15.
I have written this way
shortestPath(destinationNode, minAmount)
if(destinationNode == srcNode && minAmount < 1)
return 0
else if(destinationNode == srcNode && minAmount > 1)
return INFINITY
int destNo = destinationNode get number
int cost = INFINITY
for (int i = 0; i < destNo; i++)
if (d[i][destNo] != null)
int minimumAmountCount = minAmount;
for (int j = 0; j < marked.length(); j++)
if (marked[j] == i)
minimumAmountCount = minimumAmountCount - 1;
cost = MIN(cost, shortestPath(Node(i), minimumAmountCount);
return cost;
Basically we call this algorithm by using the our destination node and minimum amount of nodes from that list. Firstly we want to make sure that this is a recursive function and it should have a stopping point, which would be when passed destination is equal to source node(which is essentially node #0). The second case we need to check is whether we visited enough amount, so if it is less than 1(0 or negative number) then we visited enough points and return 0 as distance from node #0 to node #0 would be 0. If we did not visit enough amount then we return infinity so that algorithm would consider other paths.
So in order for the returning part to work, we have to define the destination node's number(if we consider that we have 100 nodes it would be node #99 at the initial start) and initialise cost as infinity.
Then we run a for loop that starts from 0(essentially node #0) till our current node number, this is because there are no backwards edges on the graph. By using node number we check from the matrix whether there is an existing weight for those nodes. If it exist then we initialise a variable for our current minimum amount and then run a loop and check if source to the current destination is in the list of marked nodes. If it is marked then we simply decrement the minimum amount.
For the final step we run the function again by changing destination as the current source and with the current minimum amount.
But it seems very expensive, considering the fact that the worst case complexity of nested loop takes O(|Node|^2) and total recurrence would take O(|Node|^2 * |Edges|). So is there any other efficient solution for this problem?