# Number of paths in a Directed Graph

Given a weighted directed graph $G$ with cycles and multiple edges between two nodes, I need to find how many ordered pairs $(x, y)$ exist such that the total path length from $x\ to \ y$ ends with digit $0$.
It might also happen that we can go round and round a cycle and then move further. i.e $1-2-3-1-2-3-1-2$ and $1-2$ can have different path lengths and if any one or more of them ends with $0$, we will count $(1,2) \ once$.
$\therefore$ an ordered pair can represent multiple paths, but it should be counted once.

My Approach:
Lets say $f(u, d)$ be number of ordered pairs $(u,x)$ such that the sum of weights of path from $u$ to $x$ end with digit $d \in \{0,1,2,...,9\}$.
Consider all edges from $u-v$ with weight mod 10 = $w$.
$f(u, d)$ = Sum( $f(v, (d-w+10) mod 10)$ )
This builds a recursion but I don't know about the base case.

• If you can go round a cycle, and you are allowed unlimited trips round the cycle, and there is one solution that includes the cycle: the number will be infinite - you can just keep on adding multiples of ten circuits. Commented Jan 28, 2017 at 5:26
• An ordered pair can represent multiple paths, but it should be counted once. I meant to say that if x---cycle---y ends with 0 and x---cycle---z end with 0, then we have two pairs (x,y) and (x, z). But if x--cycle--cycle---y ends with 0, we wont count it again. Commented Jan 28, 2017 at 5:29
• An adjacency matrix can be used to construct the counts of paths between two nodes of any specified length (allowing for a "round and round" cycle as you seem to wish). Commented Jan 28, 2017 at 6:00
• @hardmath I have a weighted directed graph. Commented Jan 28, 2017 at 6:13
• It is unclear what "ends with digit $0$" is supposed to mean, or how the combination of weights and multiple edges is supposed to affect your counting. I'm merely offering a standard technique as a comment. Perhaps the considerations you want can be incorporated into a Markov chain. Commented Jan 28, 2017 at 6:15

Let there be $n$ nodes in a directed graph $G$ with (integer) weights assigned to the directed edges. The problem is to determine how many ordered pairs of nodes $(x,y)$ admit a directed trail (perhaps a better word than path, since we allow repetition of nodes visited) whose length (sum of edge weights) is divisible by ten.
Construct a new directed graph $G_{10}$ with $10n$ nodes labelled $(x,d)$ where $x$ is a node in orginal graph $G$ and $d$ is a digit $0,1,\ldots,9$. For each edge of $G$ from $x$ to $y$ with weight $w$ construct ten edges in $G_{10}$ which connect $(x,d)$ to $(y,e)$ whenever $e \equiv d+w \bmod{10}$.
Then the existence of an allowed trail in $G$ from $X$ to $y$ is equivalent to the existence of a path in $G_{10}$ from $(x,0)$ to $(y,0)$. These pairs may be counted by standard techniques such as taking powers of the incidence matrix for $G_{10}$ until the nonzero entries become "saturated".