Counting the number of shortest paths through a node in a DAG

Question

I'm looking for an algorithm to count the number of paths crossing a specific node in a DAG (similar to the concept of 'betweenness'), with the following conditions and constraints:

I need to do the counting for a set of source/destination nodes in the graph, and not all nodes, i.e. for a middle node n, I want to know how many distinct shortest paths from set of nodes S to set of nodes D pass through n (and by distinct, I mean every two paths that have at least one non-common node)

What are the algorithms you may suggest to do this, considering that the DAG may be very large but sparse in edges, and hence preference is not given to deep nested loops on nodes.

Answer 1

You could use a breadth first search for each pair of Src/Dest nodes and see which of those have your given node in the path. You would have to modify the search slightly such that once you've found your shortest path, you continue to empty the queue until you reach a path that causes you to increase the size. In this way you're not bound by random chance if there are multiple shortest paths. This is only an option with non-weighted graphs, of course.