Menu
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.
366
Use BFS to determine the length of the shortest v-w-path. Then use DFS to find the number of the v-w-shortest paths such that two nodes are connected and the length of path equals to the output of BFS. But the running time of this plan is O(m+n)+O(m+n).
There is one shortest path vertex 0 to vertex 0 (from each vertex there is a single shortest path to itself), one shortest path between vertex 0 to vertex 2 (0->2), and there are 4 different shortest paths from vertex 0 to vertex 6: 0->1->3->4->6. 0->1->3->5->6. 0->2->3->4->6.
Explanation: The number of shortest path from node 1 to node 4 is 2, having cost 5.
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.
66
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
