# algorithm - undirected - total number of paths in a graph

## Algorithm to find the number of distinct paths in a directed graph (1)

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:

- Paths from
`u`

to`v`

which doesn't pass through`w`

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

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.