الگوریتم ضرب ماتریسی

فرض کنید یک گراف وزن‌دار داریم و می‌خواهیم کوتاه‌ترین فاصله‌ی دو به دوی بین رأس‌ها را بیابیم. $w[i][j]$ را وزن یال $(i, j)$ در نظر میگیریم. به ازای هر $m \le n$، مقدار $D^m[i][j]$ را برابر با طول کوتاه‌ترین مسیر از راس $i$ به $j$ که حداکثر $m$ یال دارد، در نظر می‌گیریم.

طبق تعریف به ازای هر یال با وزن $w$، $D^1=w$ است. حالا هر مسیر مثل $p$ به طول $k$ که رأس $i$ را به راس $j$ متصل می‌کند، در نظر بگیرید. با حذف رأس $j$ از انتهای مسیر یک مسیر به طول $k-1$ از $i$ به $x$ داریم؛ طوری که $x$ با $j$ هم‌سایه است. با در نظر گرفتن کوتاه‌ترین مسیر به طول حداکثر $k-1$ از $i$ به $x$ و جای‌گزینی آن در $p$، حتماً مسیر جدید کوتاه‌تر یا مساوی مسیر اولیه خواهد بود. هم‌چنین هیچ مسیر کوتاه‌تری به طول حداکثر $k$ از $i$ به $j$‌ که یال $(x, j)$ در آن باشد، وجود ندارد (چرا؟).

با این رویکرد می‌توانیم مقادیر $D^k$-ها را محاسبه‌ کنیم: $$D^k[i][j]=min(D^{k-1}[i][j], D^{k-1}[i][x]+w[x][i])$$ این عملیات را با نماد زیر نشان می‌دهیم: $$D^k=D^{k-1}.W$$ که در آن $W$، ماتریس مجاورت گراف وزن‌دار است.

الگوریتم فوق از مرتبه‌ی $O(n^4)$ است.

D1 = W
For k Form 2 To n
	For i Form 1 To n
		For j From 1 To n
			For x From 1 To n
				Dk[i][j] = min(Dk-1[i][j], Dk-1[i][x] + W[x][j])

به ازای هر $i, j$ مسیر بهینه به طول حداکثر $a+b$ را در نظر می‌گیریم. اگر راس $a$-ام مسیر را $x$ بنامیم حتماً مسیر از $i$ تا $x$، یک کوتاه‌ترین مسیر به طول حداکثر $a$ و مسیر $x$ تا $j$ یک کوتاه‌ترین مسیر به طول حداکثر $b$ است (وگرنه مسیر اولیه بهینه نبوده است). حالا ادعا می‌کنیم تساوی زیر برقرار است‌ (چرا؟): $$D^{a+b}=D^a.D^b$$ ویژگی اخیر مطرح شده برای تشابه این عملیات با ضرب ماتریس‌ها، الگوریتم محسابه‌ی توان در زمان لگاریتمی یادآور می‌شود. دقت کنید که هدف ما محاسبه‌ی کوتاه‌ترین مسیر‌های بین هر زوج از رئوس گراف است و در نهایت فقط به $D^n$ نیاز داریم.

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

در الگوریتم اخیر تابع MatrixMin از مرتبه‌ی $ O(n^3) $ است و این تابع $ lg n $ بار اجرا می‌شود. پس مرتبه‌ی نهایی الگوریتم به $ O(n^3 lg n) $ بهبود یافت.