یک گراف جهت‌دار داریم که می‌تواند یال چندگانه یا طوقه نیز داشته باشد (گراف های بدون جهت هم با گذاشتن دو یال جهت دار به ازای هر یال بی جهت، جهت دار میکنیم). میخواهیم تعداد گشت‌ها به طول $m$ را بین هر دو راس در این گراف پیدا کنیم.

برای این کار ماتریس مجاورت گراف را ماتریس $A$ در نظر میگیریم. آن را به توان $m$ می‌رسانیم. در ماتریس $A$ درایه $(i,j)$ نشان دهنده تعداد گشت های به طول دقیقا $m$ بین دو راس $i$ و $j$ است.

درستی این الگوریتم را به استقرا ثابت می‌کنیم:

پایه استقرا: در ماتریس $ A_1=A $ درایه$(i,j)$ نشان دهنده تعداد گشت‌های بین دو راس $i$ و $j$ به طول 1 است. چون گشت به طول 1 فقط میتواند یک یال باشد، پس تعداد گشت‌های به طول 1 بین دو راس، برابر تعداد یال های بین این دو است که در ماتریس مجاورت درایه مربوطه همین را نشان میدهد.

فرض استقرا: حکم به ازای $m - 1$ درست است.

گام استقرا : یک گشت به طول $m$ از $i$ به $j$ را در نظر بگیرید، $m - 1$ یال اول آن یک گشت به طول $m - 1$ با شروع از $i$ است و با یک یال آخر به راس $j$ میرسد. پس راس پایانی گشت $m - 1$ تایی همسایه راس $j$ است، به عبارتی بین راس پایانی گشت $m - 1$ تایی و راس $j$ گشت به طول یک وجود دارد. حال به ازای هر راس در گراف تعداد گشت های بین راس $i$ و آن راس را در $A_{m-1}$ داریم، با ضرب این تعداد در گشت های به طول 1 بین این راس و $j$ و جمع همه مقادیر راس ها، تعداد گشت‌های به طول $m$ بین دو راس $i$ و $j$ بدست می‌آید. این مقدار برابر درایه $(i,j)$ ماتریس $A_m$ است که از ضرب $Aـ{m - 1}$ در $A_1$ بدست آمده است.

برای بدست آوردن تعداد گشت های به طول $m$ بین هر دو راس، باید ماتریس $A_m$ را محاسبه کنیم. میدانیم که ضرب دو ماتریس $n$ در $n$ در هم از $O(n^3)$ است. برای به توان $m$ رساندن کافی است $log(m)$ بار ضرب انجام دهیم. پس کل عملیات از $O(n^3log(m))$ است.

Function MatrixMultiply(A, B):
	For i Form 1 To n
		For j From 1 To n
			C[i][j] = 0
			For x From 1 To n
				C[i][j] += A[i][x] * B[x][j]
Function Power(D, k):
	if k = 1
		return D
	tmp = Power(D, k/2)
	if (k % 2 = 0) :
		return MatrixMultiply(tmp, tmp)
	else
		tmp = MatrixMulyiply(tmp, tmp)
		return MatrixMultiply(tmp, D)