  Max-plus algebra is a semiring with addition $a\oplus b = \max(a,b)$ and
multiplication $a\otimes b = a+b$. It is applied in cases, such as
combinatorial optimization and discrete event systems. We consider the power of
max-plus square matrices, which is equivalent to obtaining the all-pair maximum
weight paths with a fixed length in the corresponding weighted digraph. Each
$n$-by-$n$ matrix admits the CSR expansion that decomposes the matrix into a
sum of at most $n$ periodic terms after $O(n^{2})$ times of powers. In this
study, we propose an $O(n(m+n \log n))$ time algorithm for the CSR expansion,
where $m$ is the number of nonzero entries in the matrix, which improves the
$O(n^{4} \log n)$ algorithm known for this problem. Our algorithm is based on
finding the roots of the characteristic polynomial of the max-plus matrix.
These roots play a similar role to the eigenvalues of the matrix, and become
the growth rates of the terms in the CSR expansion.
