پرش به محتویات

تعداد مسیرها با طول ثابت / کوتاه‌ترین مسیرها با طول ثابت

مقاله زیر راه‌حل‌هایی برای این دو مسئله ارائه می‌دهد که بر پایه‌ی یک ایده ساخته شده‌اند: کاهش مسئله به ساخت یک ماتریس و محاسبه‌ی پاسخ با استفاده از ضرب ماتریسی معمولی یا یک ضرب اصلاح‌شده.

تعداد مسیرها با طول ثابت

یک گراف جهت‌دار و بدون وزن $G$ با $n$ رأس و یک عدد صحیح $k$ به ما داده شده است. مسئله به این صورت است: برای هر جفت رأس $(i, j)$ باید تعداد مسیرها با طول دقیقاً $k$ بین این دو رأس را پیدا کنیم. مسیرها لزوماً ساده نیستند، یعنی می‌توان رأس‌ها و یال‌ها را در یک مسیر چندین بار پیمود.

فرض می‌کنیم که گراف با یک ماتریس مجاورت مشخص شده است، یعنی ماتریس $G[][]$ با ابعاد $n \times n$، که در آن هر درایه $G[i][j]$ برابر با ۱ است اگر رأس $i$ با یک یال به $j$ متصل باشد، و در غیر این صورت برابر با ۰ است. الگوریتم زیر در حالت وجود یال‌های چندگانه نیز کار می‌کند: اگر یک جفت رأس $(i, j)$ با $m$ یال به هم متصل باشند، می‌توانیم این موضوع را با قرار دادن $G[i][j] = m$ در ماتریس مجاورت ثبت کنیم. همچنین این الگوریتم در صورتی که گراف شامل طوقه باشد (طوقه یالی است که یک رأس را به خودش متصل می‌کند) نیز کار می‌کند.

واضح است که ماتریس مجاورت ساخته‌شده، پاسخ مسئله برای حالت $k = 1$ است. این ماتریس تعداد مسیرهای با طول ۱ بین هر جفت رأس را در خود دارد.

ما راه‌حل را به صورت تکراری می‌سازیم: فرض کنید پاسخ را برای یک $k$ مشخص می‌دانیم. در اینجا روشی را برای ساختن پاسخ برای $k + 1$ توصیف می‌کنیم. ماتریس مربوط به حالت $k$ را با $C_k$ و ماتریسی که می‌خواهیم بسازیم را با $C_{k+1}$ نشان می‌دهیم. با استفاده از فرمول زیر می‌توانیم هر درایه‌ی $C_{k+1}$ را محاسبه کنیم:

$$C_{k+1}[i][j] = \sum_{p = 1}^{n} C_k[i][p] \cdot G[p][j]$$

به راحتی می‌توان دید که این فرمول چیزی جز حاصل‌ضرب ماتریس‌های $C_k$ و $G$ را محاسبه نمی‌کند:

$$C_{k+1} = C_k \cdot G$$

بنابراین، راه‌حل مسئله را می‌توان به صورت زیر نمایش داد:

$$C_k = \underbrace{G \cdot G \cdots G}_{k \text{ بار}} = G^k$$

لازم به ذکر است که ضرب‌های ماتریسی را می‌توان با استفاده از توان‌رسانی دودویی (Binary exponentiation) به طور کارآمد به توان‌های بالا رساند. این روش راه‌حلی با پیچیدگی $O(n^3 \log k)$ ارائه می‌دهد.

کوتاه‌ترین مسیرها با طول ثابت

یک گراف جهت‌دار وزن‌دار $G$ با $n$ رأس و یک عدد صحیح $k$ به ما داده شده است. برای هر جفت رأس $(i, j)$ باید طول کوتاه‌ترین مسیری را پیدا کنیم که دقیقاً از $k$ یال تشکیل شده باشد.

فرض می‌کنیم که گراف با یک ماتریس مجاورت مشخص شده است، یعنی از طریق ماتریس $G[][]$ با ابعاد $n \times n$ که در آن هر درایه $G[i][j]$ حاوی طول یال از رأس $i$ به رأس $j$ است. اگر یالی بین دو رأس وجود نداشته باشد، درایه متناظر در ماتریس برابر با بی‌نهایت ($\infty$) خواهد بود.

واضح است که ماتریس مجاورت در این شکل، پاسخ مسئله برای $k = 1$ است. این ماتریس طول کوتاه‌ترین مسیرهای بین هر جفت رأس را در خود دارد، یا اگر مسیری متشکل از یک یال وجود نداشته باشد، مقدار آن $\infty$ است.

باز هم می‌توانیم راه‌حل مسئله را به صورت تکراری بسازیم: فرض کنید پاسخ را برای یک $k$ مشخص می‌دانیم. نشان می‌دهیم که چگونه می‌توانیم پاسخ را برای $k+1$ محاسبه کنیم. ماتریس برای $k$ را با $L_k$ و ماتریسی که می‌خواهیم بسازیم را با $L_{k+1}$ نشان می‌دهیم. سپس فرمول زیر هر درایه از $L_{k+1}$ را محاسبه می‌کند:

$$L_{k+1}[i][j] = \min_{p = 1 \ldots n} \left(L_k[i][p] + G[p][j]\right)$$

با نگاهی دقیق‌تر به این فرمول، می‌توان شباهتی با ضرب ماتریسی پیدا کرد: در واقع، ماتریس $L_k$ در ماتریس $G$ ضرب می‌شود، با این تفاوت که به جای عمل جمع از کمینه (minimum) و به جای عمل ضرب از جمع به عنوان عملگر داخلی استفاده می‌شود.

$$L_{k+1} = L_k \odot G,$$

که در آن عملگر $\odot$ به صورت زیر تعریف می‌شود:

$$A \odot B = C~~\Longleftrightarrow~~C_{i j} = \min_{p = 1 \ldots n}\left(A_{i p} + B_{p j}\right)$$

بنابراین، راه‌حل مسئله را می‌توان با استفاده از این ضرب اصلاح‌شده نمایش داد:

$$L_k = \underbrace{G \odot \ldots \odot G}_{k~\text{بار}} = G^{\odot k}$$

لازم به ذکر است که می‌توانیم این توان‌رسانی را نیز با استفاده از توان‌رسانی دودویی (Binary exponentiation) به طور کارآمد محاسبه کنیم، زیرا این ضرب اصلاح‌شده به وضوح شرکت‌پذیر است. بنابراین، این راه‌حل نیز دارای پیچیدگی $O(n^3 \log k)$ است.

تعمیم مسائل برای مسیرهایی با طول حداکثر $k$

راه‌حل‌های بالا، مسائل را برای یک $k$ ثابت حل می‌کنند. با این حال، می‌توان این راه‌حل‌ها را برای حل مسائلی که در آن‌ها مسیرها مجاز به داشتن حداکثر $k$ یال هستند، تطبیق داد.

این کار را می‌توان با تغییر جزئی در گراف ورودی انجام داد.

ما هر رأس را تکثیر می‌کنیم: برای هر رأس $v$، یک رأس دیگر $v'$ ایجاد کرده و یال $(v, v')$ و طوقه $(v', v')$ را اضافه می‌کنیم. تعداد مسیرها بین $i$ و $j$ با حداکثر $k$ یال، برابر است با تعداد مسیرها بین $i$ و $j'$ با دقیقاً $k + 1$ یال، زیرا یک تناظر یک‌به‌یک وجود دارد که هر مسیر $[p_0 = i,~p_1,~\ldots,~p_{m-1},~p_m = j]$ با طول $m \le k$ را به مسیر $[p_0 = i,~p_1,~\ldots,~p_{m-1},~p_m = j, j', \ldots, j']$ با طول $k + 1$ نگاشت می‌دهد.

همین ترفند را می‌توان برای محاسبه کوتاه‌ترین مسیرها با حداکثر $k$ یال نیز به کار برد. ما دوباره هر رأس را تکثیر کرده و دو یال ذکر شده را با وزن ۰ اضافه می‌کنیم.