Count Paths via Matrix Power

Problem

Given a directed graph with n nodes and edges as [u, v] pairs, return the number of walks of exactly the given length from start to end.

Build the adjacency matrix, where parallel edges increase an entry, raise it to the length with fast matrix exponentiation, and read the entry [start][end]. Length 0 gives 1 when start equals end.

Hint

The (i, j) entry of the adjacency matrix raised to power L counts walks of length L.

Test cases

case 1

in: [3,[[0,1],[1,2],[2,0]],3,0,0]

expected: 1

case 2

in: [3,[[0,1],[1,2],[2,0]],6,0,0]

expected: 1

case 3

in: [3,[[0,1],[1,2]],2,0,2]

expected: 1

case 4

in: [1,[],0,0,0]

expected: 1

case 5

in: [2,[[0,1],[1,0]],2,0,0]

expected: 1

Starter codePython

def count_paths_matrix_power(n, edges, length, start, end):
    # Your code here
    pass

5 test cases · run your code against them in the editor