Algorithm to find the number of distinct paths in a directed graph

Question

I have a directed graph, what algorithm can i use to find the number of distinct acyclic paths between 2 particular vertices, and count the maximum times any path is used in these distinct paths? Two paths are distinct if they either visit a different number of vertices or visit vertices in a different order.

Answer 1

Breadth-first search?

Seriously, when asking about every possible path, only a brute-force way trying out every possible path will give you a result.

Answer 2

If you follow a slightly modified Dijkstra's algorithm, you can have an all-pair solution.

Explanation: Paths from u to v is the sum of the following:

1. Paths from u to v which doesn't pass through w
2. Paths which go through w = number of paths from u to w times number of paths from w to v

Initialise the matrix with zeros except when there is an edge from i to j (which is 1). Then the following algorithm will give you the result (all-pair-path-count)

for i = 1 to n:
    for j = 1 to n:
        for k = 1 to n:
            paths[i][i] += paths[i][k] * paths[k][j]

Needless to say : O(n^3)

Eager to read a single pair solution. :)

Answer 3

Found the solution to an identical problem on this link. It uses DFS. Have implemented it and it works well.

http://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices