13

Possible Duplicate:
Graph Algorithm To Find All Connections Between Two Arbitrary Vertices

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.

Community
  • 1
  • 1
Pranav
  • 3,340
  • 8
  • 35
  • 48
  • 7
    IMHO This need not to be a duplicate. There is a difference between knowing the number of values (integer) and knowing all the values (a set of lists of nodes). For my purpose, even a reasonable guess of the number (upper bound) is OK so for me this is not a duplicate. – danatel Jul 13 '11 at 06:10
  • 3
    [Graph Algorithm To Find All Connections Between Two Arbitrary Vertices](http://stackoverflow.com/q/58306) is not a duplicate at all: enumerating and counting are different problems, and a directed graph is a different beast from an undirected graph. Regarding the complexity of counting simple paths, see [How hard is counting the number of simple paths between two nodes in a directed graph?](http://cs.stackexchange.com/q/423) on [cs.se]. – Gilles 'SO- stop being evil' Mar 15 '12 at 19:57
  • I agree with Danatel - for large graphs, it is undesirable to count an enumeration of all possible paths. – Andrew Buss Nov 20 '12 at 15:43

1 Answers1

5

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. :)

ThisIsMeMoony
  • 372
  • 1
  • 6