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

الگوریتم فلوید-وارشال

یک گراف وزن‌دار جهت‌دار یا بدون جهت $G$ با $n$ رأس داده شده است. هدف، پیدا کردن طول کوتاه‌ترین مسیر $d_{ij}$ بین هر جفت رأس $i$ و $j$ است.

گراف می‌تواند یال‌هایی با وزن منفی داشته باشد، اما دور با وزن منفی نداشته باشد.

اگر چنین دور منفی‌ای وجود داشته باشد، می‌توان این دور را بارها و بارها پیمود و در هر تکرار، هزینه مسیر را کمتر کرد. بنابراین می‌توان مسیرهای خاصی را به طور دلخواه کوچک کرد، یا به عبارت دیگر کوتاه‌ترین مسیر تعریف نشده است. این به طور خودکار به این معنی است که یک گراف بدون جهت نمی‌تواند هیچ یال با وزن منفی داشته باشد، زیرا چنین یالی خود یک دور منفی تشکیل می‌دهد چون می‌توانید به هر تعدادی که بخواهید در امتداد آن یال به عقب و جلو حرکت کنید.

این الگوریتم همچنین می‌تواند برای تشخیص وجود دورهای منفی استفاده شود. گراف دارای یک دور منفی است اگر در پایان الگوریتم، فاصله از یک رأس $v$ به خودش منفی باشد.

این الگوریتم به طور همزمان در مقالاتی توسط Robert Floyd و Stephen Warshall در سال ۱۹۶۲ منتشر شد. با این حال، در سال ۱۹۵۹، Bernard Roy اساساً همان الگوریتم را منتشر کرد، اما انتشار آن مورد توجه قرار نگرفت.

شرح الگوریتم

ایده اصلی الگوریتم این است که فرآیند پیدا کردن کوتاه‌ترین مسیر بین هر دو رأس را به چندین مرحله افزایشی تقسیم کنیم.

بیایید رأس‌ها را از ۱ تا $n$ شماره‌گذاری کنیم. ماتریس فاصله‌ها $d[ ][ ]$ است.

قبل از مرحله $k$-ام ($k = 1 \dots n$)، مقدار $d[i][j]$ برای هر جفت رأس $i$ و $j$، طول کوتاه‌ترین مسیر بین رأس $i$ و رأس $j$ را ذخیره می‌کند، به طوری که این مسیر فقط شامل رأس‌های $\{1, 2, ..., k-1\}$ به عنوان رأس‌های میانی باشد.

به عبارت دیگر، قبل از مرحله $k$-ام، مقدار $d[i][j]$ برابر با طول کوتاه‌ترین مسیر از رأس $i$ به رأس $j$ است، اگر این مسیر مجاز باشد فقط از رأس‌هایی با شماره‌های کوچکتر از $k$ عبور کند (ابتدا و انتهای مسیر با این ویژگی محدود نمی‌شوند).

اطمینان از برقراری این ویژگی برای مرحله اول آسان است. برای $k = 0$، می‌توانیم ماتریس را با $d[i][j] = w_{i j}$ پر کنیم اگر یالی بین $i$ و $j$ با وزن $w_{i j}$ وجود داشته باشد و اگر یالی وجود نداشته باشد، $d[i][j] = \infty$ قرار می‌دهیم. در عمل، $\infty$ یک مقدار بزرگ خواهد بود. همانطور که بعداً خواهیم دید، این یک پیش‌نیاز برای الگوریتم است.

حال فرض کنید در مرحله $k$-ام هستیم و می‌خواهیم ماتریس $d[ ][ ]$ را محاسبه کنیم تا شرایط لازم برای مرحله $(k + 1)$-ام را برآورده کند. باید فاصله‌ها را برای برخی جفت رأس‌های $(i, j)$ اصلاح کنیم. دو حالت اساساً متفاوت وجود دارد:

  • کوتاه‌ترین مسیر از رأس $i$ به رأس $j$ با رأس‌های میانی از مجموعه $\{1, 2, \dots, k\}$ با کوتاه‌ترین مسیر با رأس‌های میانی از مجموعه $\{1, 2, \dots, k-1\}$ یکسان است.

    در این حالت، $d[i][j]$ در طول این گذار تغییر نخواهد کرد.

  • کوتاه‌ترین مسیر با رأس‌های میانی از مجموعه $\{1, 2, \dots, k\}$ کوتاه‌تر است.

    این بدان معناست که مسیر جدید و کوتاه‌تر از رأس $k$ عبور می‌کند. این یعنی می‌توانیم کوتاه‌ترین مسیر بین $i$ و $j$ را به دو مسیر تقسیم کنیم: مسیر بین $i$ و $k$ و مسیر بین $k$ و $j$. واضح است که هر دوی این مسیرها فقط از رأس‌های میانی مجموعه $\{1, 2, \dots, k-1\}$ استفاده می‌کنند و از این نظر کوتاه‌ترین مسیرها هستند. بنابراین، ما قبلاً طول این مسیرها را محاسبه کرده‌ایم و می‌توانیم طول کوتاه‌ترین مسیر بین $i$ و $j$ را به صورت $d[i][k] + d[k][j]$ محاسبه کنیم.

با ترکیب این دو حالت، متوجه می‌شویم که می‌توانیم طول همه جفت‌های $(i, j)$ را در مرحله $k$-ام به روش زیر دوباره محاسبه کنیم:

$$d_{\text{new}}[i][j] = min(d[i][j], d[i][k] + d[k][j])$$

بنابراین، تمام کاری که در مرحله $k$-ام لازم است، پیمایش تمام جفت رأس‌ها و محاسبه مجدد طول کوتاه‌ترین مسیر بین آنها است. در نتیجه، پس از مرحله $n$-ام، مقدار $d[i][j]$ در ماتریس فاصله، طول کوتاه‌ترین مسیر بین $i$ و $j$ است، یا اگر مسیری بین رأس‌های $i$ و $j$ وجود نداشته باشد، برابر با $\infty$ خواهد بود.

نکته آخر - نیازی به ایجاد یک ماتریس فاصله جداگانه $d_{\text{new}}[ ][ ]$ برای ذخیره‌سازی موقت کوتاه‌ترین مسیرهای مرحله $k$-ام نیست، یعنی تمام تغییرات را می‌توان مستقیماً در ماتریس $d[ ][ ]$ در هر مرحله انجام داد. در واقع، در هر مرحله $k$-ام ما حداکثر در حال بهبود فاصله هر مسیر در ماتریس فاصله هستیم، بنابراین نمی‌توانیم طول کوتاه‌ترین مسیر را برای هر جفت رأسی که قرار است در مرحله $(k+1)$-ام یا بعد از آن پردازش شوند، بدتر کنیم.

پیچیدگی زمانی این الگوریتم به وضوح $O(n^3)$ است.

پیاده‌سازی

فرض کنید $d[][]$ یک آرایه دوبعدی به اندازه $n \times n$ است که مطابق با مرحله صفرم همانطور که قبلاً توضیح داده شد، پر شده است. همچنین برای هر $i$ در مرحله صفرم، $d[i][i] = 0$ قرار می‌دهیم.

سپس الگوریتم به صورت زیر پیاده‌سازی می‌شود:

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

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

اما اگر یال‌هایی با وزن منفی در گراف وجود داشته باشد، باید اقدامات ویژه‌ای انجام شود. در غیر این صورت، مقادیر حاصل در ماتریس ممکن است به شکل $\infty - 1$، $\infty - 2$ و غیره باشند که البته هنوز نشان‌دهنده عدم وجود مسیر بین رأس‌های مربوطه است. بنابراین، اگر گراف یال‌های با وزن منفی دارد، بهتر است الگوریتم فلوید-وارشال را به روش زیر بنویسیم تا از گذارهایی با استفاده از مسیرهای غیرموجود جلوگیری کند.

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (d[i][k] < INF && d[k][j] < INF)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

بازیابی دنباله رأس‌ها در کوتاه‌ترین مسیر

به راحتی می‌توان اطلاعات اضافی را نگهداری کرد که با آن بتوان کوتاه‌ترین مسیر بین هر دو رأس داده شده را به صورت دنباله‌ای از رأس‌ها بازیابی کرد.

برای این کار، علاوه بر ماتریس فاصله $d[ ][ ]$، باید یک ماتریس پیشینیان $p[ ][ ]$ نیز نگهداری شود که شماره مرحله‌ای را که در آن کوتاه‌ترین فاصله بین دو رأس برای آخرین بار اصلاح شده است، در خود ذخیره می‌کند. واضح است که شماره مرحله، چیزی جز یک رأس در وسط کوتاه‌ترین مسیر مورد نظر نیست. اکنون فقط باید کوتاه‌ترین مسیر بین رأس‌های $i$ و $p[i][j]$ و بین $p[i][j]$ و $j$ را پیدا کنیم. این منجر به یک الگوریتم بازسازی بازگشتی ساده برای کوتاه‌ترین مسیر می‌شود.

حالت وزن‌های حقیقی

اگر وزن یال‌ها صحیح نباشد و حقیقی باشد، لازم است خطاهایی را که هنگام کار با انواع داده ممیز شناور (float) رخ می‌دهد، در نظر گرفت.

الگوریتم فلوید-وارشال این اثر ناخوشایند را دارد که خطاها به سرعت انباشته می‌شوند. در واقع، اگر در مرحله اول خطایی به اندازه $\delta$ وجود داشته باشد، این خطا ممکن است در تکرار دوم به $2 \delta$، در تکرار سوم به $4 \delta$ و به همین ترتیب گسترش یابد.

برای جلوگیری از این مشکل، می‌توان الگوریتم را طوری تغییر داد که خطا (EPS = $\delta$) را با استفاده از مقایسه زیر در نظر بگیرد:

if (d[i][k] + d[k][j] < d[i][j] - EPS)
    d[i][j] = d[i][k] + d[k][j];

حالت دورهای منفی

به طور رسمی، الگوریتم فلوید-وارشال برای گراف‌های حاوی دور(های) با وزن منفی قابل استفاده نیست. اما برای تمام جفت رأس‌های $i$ و $j$ که مسیری از $i$ شروع شده، از یک دور منفی عبور کرده و به $j$ ختم شود وجود نداشته باشد، الگوریتم همچنان به درستی کار خواهد کرد.

برای جفت رأس‌هایی که به دلیل وجود دور منفی در مسیر بین آنها پاسخی وجود ندارد، الگوریتم فلوید هر عددی را (شاید بسیار منفی، اما نه لزوماً) در ماتریس فاصله ذخیره می‌کند. با این حال، می‌توان الگوریتم فلوید-وارشال را بهبود بخشید تا با دقت بیشتری با چنین جفت رأس‌هایی برخورد کند و آنها را، به عنوان مثال، با $-\text{INF}$ مشخص کند.

این کار را می‌توان به روش زیر انجام داد: الگوریتم فلوید-وارشال معمول را برای گراف داده شده اجرا می‌کنیم. آنگاه کوتاه‌ترین مسیر بین رأس‌های $i$ و $j$ وجود ندارد، اگر و تنها اگر، رأسی مانند $t$ وجود داشته باشد که هم از $i$ قابل دسترس باشد و هم $i$ از آن قابل دسترس باشد، و برای آن $d[t][t] < 0$ باشد.

علاوه بر این، هنگام استفاده از الگوریتم فلوید-وارشال برای گراف‌های با دور منفی، باید به خاطر داشت که ممکن است شرایطی پیش بیاید که در آن فاصله‌ها به سرعت به صورت نمایی به سمت مقادیر منفی میل کنند. بنابراین، باید با محدود کردن حداقل فاصله به یک مقدار مشخص (مانند $-\text{INF}$)، از سرریز عدد صحیح (integer overflow) جلوگیری کرد.

برای کسب اطلاعات بیشتر در مورد یافتن دورهای منفی در یک گراف، به مقاله جداگانه پیدا کردن یک دور منفی در گراف مراجعه کنید.

مسائل تمرینی