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


===== تعریف =====

فرض کنید یک گراف وزن‌دار داریم و می‌خواهیم کوتاه‌ترین فاصله‌ی دو به دوی بین رأس‌ها را بیابیم. $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)$ است.

===== شبه کد (۱) =====

<code>
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])
</code>

===== الگوریتم به‌تر =====

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


===== شبه کد (۲) =====

<code>
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)
</code>


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

===== مسائل نمونه =====

===== مراجع =====