Shortest path that passes through specific node(s)

Question

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?

Answer 1

Compute the shortest path between all pairs of the twelve special nodes (nodes 1, 100, and all ten of your particular nodes), and use these as edge lengths in a new graph consisting only of these twelve nodes. Now, you have a graph containing twelve nodes, and you want to find the shortest path from 1 to 100 that uses at least five other nodes. Now, you can use your algorithm (which I think is just dynamic programming) on this graph, which is much smaller. The solution on the new graph will give a solution for the original graph, which you can find by replacing the edges in the solution in the new graph with the shortest paths you computed in the first step.

For your example, we will have 4 nodes in the new graph. The edge lengths in the new graph are: 0-1:5, 0-4:6, 0-5:11, 1-4:5, 1-5:10, 4-5:5. These correspond to the shortest paths between nodes $i$ and $j$ in the original graph. The shortest path including one node from the list is 0-4-5, which has length 11. Now, replacing each edge in this path with the path computed in the first step gives the path 0-3-4-5 in the original graph.

Answer 2

If all you have is 100 nodes, and your arcs are given or easy to compute: don't worry about it.

If not: your graph is probably very sparse (many more pairs of nodes with arcs than without arcs). So use linked lists or some other data structure that allows you to iterate over just arcs, not having to skip non-arcs. The names of such data structures are language dependent; various types of Java or C# Lists or Dictionaries quality, as do e.g. hashes in Perl or associative arrays in PHP.

I'd use them to build a mapping from nodes to forward arcs (i.e. pairs of cost and destination node), and another from nodes to backward arcs.

I'd allocate two more to hold the node-to-node distances from each node to each intermediate node, and from each intermediate node to each node, and compute them using the standard algorithm (Floyd's, also known as Dijkstra's, or, erroneously, Warshall's).

I'd allocate one more to hold the final node-to-node distances, and compute them as $$d(x,y) = min_{z \in I}(d(x,z) + d(z,y))$$ for the intermediate nodes $I$.