Abstract:
In this paper, we present an algorithm for finding the number of paths on a directed graph that start at an arbitrary subset of its vertices. The algorithm is based on the ideas underlying the construction of Pascal's triangle. The complexity of the algorithm coincides with the complexity of the well-known Dijkstra algorithm for finding shortest paths on graphs. We also generalize the algorithm proposed to the problem on graphs with reachability constraints.