بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی CodeCup 2018

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسئله‌ی انتخابات

الگوریتم فلوید-وارشال - الگوریتمستان
الگوریتمستان
1314.625.00
  »  

       

آشنایی با الگوریتم فلوید-وارشال برای یافتن کوتاهترین مسیرهای گراف با قطعه کد نمونه به زبان برنامه‌نویسی ++C

الگوریتم فلوید-وارشال (Floyd-Warshall) یک الگوریتم مبتنی بر روش برنامه‌نویسی پویا برای محاسبه‌ی کوتاهترین مسیر بین هر دو جفت گره گراف‌های وزن‌دار است. دو الگوریتم رایج دایکسترا و بلمن-فورد روش‌های محاسبه‌ی کوتاهترین مسیر از مبدأ ثابت هستند که در صورت تکرار آنها به ازای هر گره عملکردی همانند الگوریتم فلوید-وارشال دارند. اما این الگوریتم ویژگی‌هایی دارد که آن را برجسته می‌کند:

    1) پیاده‌سازی ساده‌تری دارد.

    2) بر خلاف الگوریتم دایکسترا برای گراف‌هایی شامل یال با وزن منفی نیز قابل استفاده است.

    3) در حالت کلی مرتبه‌ی زمانی بهتری نسبت به الگوریتم بلمن-فورد دارد.

    4) همانند الگوریتم بلمن-فورد قابلیت تشخیص دور منفی را دارد.

    فرض کنید ماتریس مجاورت گراف را با $M_{ n \times n } $ و گره‌های گراف را به صورت $\{ v_1, v_2, v_3, \cdots, v_n \} $ نمایش دهیم. اگر ماتریس $D^{(k)}_{n \times n}$ معرف ماتریس طول کوتاهترین مسیر بین گره‌های گراف تنها با اجازه‌ی عبور از گره‌های $\{v_1,v_2,v_3,\cdots,v_k\}$ باشد، ماتریس $D^{(n)}$ جواب مسئله خواهد بود. همچین $D^{(0)}$ همان $M$ است (چرا؟). پس محاسبه‌ی کوتاهترین مسیر بین گره‌ها به محاسبه‌ی ماتریس $D^{(n)}$ تبدیل می‌شود.

    کوتاهترین مسیر از گره $v_i$ به گره $v_j$ با اجازه‌ی عبور از گره $v_1$ یا مسیر مستقیم بین آن دو (با اندازه‌ی $M_{ij}$) است یا مسیری که از گره $v_1$ (با اندازه‌ی $M_{i1}+M_{1j}$) می‌گذرد؛ یعنی:

\[D^{(1)}_{ij}= min\{ M_{ij}, M_{i1}+M_{1j} \} \]

    با استفاده از این رابطه درایه‌های ماتریس $D^{(1)}$ از روی ماتریس مجاورت (یا همان ماتریس $D^{(0)}$) قابل محاسبه است. درایه‌های ماتریس $D^{(2)}$ طول کوتاهترین مسیرها با اجازه‌ی عبور از گره‌های $v_1$ و $v_2$ است. چنین مسیرهایی یا بدون استفاده از گره $v_2$ هستند (یعنی همان $D^{(1)}_{ij}$) یا با عبور از این گره. اگر از این گره استفاده شود، طول کوتاهترین مسیر $D^{(1)}_{i2} + D^{(1)}_{2j} $ خواهد بود؛ چرا که $D^{(1)}_{i2}$ طول کوتاهترین مسیر از گره $v_i$ به این گره و $D^{(1)}_{2j} $ طول کوتاهترین مسیر از آن به گره $v_j$ است؛ پس:

\[D^{(2)}_{ij}= min\{ D^{(1)}_{ij}, D^{(1)}_{i2}+D^{(1)}_{2j} \} \]

    این استدلال برای محاسبه‌ی هر کدام از ماتریس‌های $D^{(k)}$ برقرار است و در حالت کلی می‌توان نوشت:

\[D^{(k)}_{ij}= min\{ D^{(k-1)}_{ij}, D^{(k-1)}_{ik}+D^{(k-1)}_{kj} \} \; ; \qquad 0 < k \leq n \;, \; D^{(0)} = M \]

    رابطه‌ی فوق مبنای کار الگوریتم فلوید-وارشال برای محاسبه‌ی طول کوتاهترین مسیر بین گره‌های یک گراف است.

      

مسیریابی با استفاده از الگوریتم فلوید-وارشال

  [بازگشت به فهرست]

الگوریتم بحث شده تنها برای محاسبه‌ی اندازه‌ی کوتاهترین مسیر بین گره‌های گراف بوده و امکان تشخیص گره‌های این مسیر را ندارد. برای رفع این مشکل از ماتریس $ P_{n \times n}$ استفاده می‌شود که در ابتدا همه‌ی عناصر آن صفر است. طی محاسبات ماتریس‌های $D^{(k)}$ اگر گره $k$ در کوتاهترین مسیر بین دو گره $i$ و $j$ انتخاب شد مقدار $k$ در $P_{ij}$ قرار داده می‌شود. به این ترتیب در انتهای الگوریتم یک شماره‌ی گره واسط بین دو گره $i$ و $j$ در درایه‌ی $P_{ij}$ موجود است. این درایه تنها در شرایطی صفر خواهد ماند که یا مسیری بین دو گره وجود نداشته، یا کوتاهترین مسیر یال مستقیم بین آن دو باشد. با مشخص شدن این گره واسط، تشخیص مسیر بهینه از مبدأ به مقصد تبدیل به تشخیص مسیر بهینه از مبدأ به این گره و از این گره به مقصد می‌گردد. تشخیص چنین مسیرهایی نیز از طریق همین ماتریس به صورت بازگشتی انجام می‌گیرد. به عنوان مثال برای گراف زیر:

      

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

      

    ماتریس‌های مجاورت ($M$)، اندازه‌ی مسیرهای بهینه ($D$) و $P$ به این ترتیب است:

\[M = \begin{pmatrix} 0 & 1 & 2 & 4 & \infty & \infty & \infty & \infty  \\ \infty & 0 & \infty & \infty & \infty & \infty & 9 & 9  \\ 2 & \infty & 0 & 3 & \infty & \infty & \infty & \infty  \\ \infty & \infty & \infty & 0 & 2 & \infty & 4 & \infty  \\ \infty & \infty & \infty & \infty & 0 & \infty & 1 & \infty  \\ \infty & \infty & \infty & \infty & 6 & 0 & \infty & \infty  \\ 7 & 8 & \infty & \infty & 1 & 7 & 0 & 2  \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & 0 \end{pmatrix}\]

\[D = \begin{pmatrix} 0 & 1 & 2 & 4 & 6 & 14 & 7 & 9  \\ 16 & 0 & 18 & 20 & 10 & 16 & 9 & 9  \\ 2 & 3 & 0 & 3 & 5 & 13 & 6 & 8  \\ 10 & 11 & 12 & 0 & 2 & 10 & 3 & 5  \\ 8 & 9 & 10 & 12 & 0 & 8 & 1 & 3  \\ 14 & 15 & 16 & 18 & 6 & 0 & 7 & 9  \\ 7 & 8 & 9 & 11 & 1 & 7 & 0 & 2  \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & 0 \end{pmatrix} \qquad P = \begin{pmatrix} 0 & 0 & 0 & 0 & 4 & 7 & 5 & 7  \\ 7 & 0 & 7 & 7 & 7 & 7 & 0 & 0  \\ 0 & 1 & 0 & 0 & 4 & 7 & 5 & 7  \\ 7 & 7 & 7 & 0 & 0 & 7 & 5 & 7  \\ 7 & 7 & 7 & 7 & 0 & 7 & 0 & 7  \\ 7 & 7 & 7 & 7 & 0 & 0 & 5 & 7  \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0  \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}\]

    بر اساس این اطلاعات، کوتاهترین مسیر از گره شماره‌ی 1 به گره شماره‌ی 7 به این ترتیب به دست می‌آید:

    1) کوتاهترین مسیر از گره شماره‌ی 1 به گره شماره‌ی 7 از گره شماره‌ی 5 (درایه‌ی $P_{17}$) عبور می‌کند.

\[v_1 \rightarrow \cdots \rightarrow v_5 \rightarrow \cdots \rightarrow v_7 \]

    2) کوتاهترین مسیر از گره شماره‌ی 5 به گره شماره‌ی 7 یال مستقیم آنها است (درایه‌ی $P_{57}$).

\[v_1 \rightarrow \cdots \rightarrow v_5 \rightarrow v_7 \]

    3) کوتاهترین مسیر از گره شماره‌ی 1 به گره شماره‌ی 5 از گره شماره‌ی 4 (درایه‌ی $P_{15}$) عبور می‌کند.

\[v_1 \rightarrow \cdots  \rightarrow v_4 \rightarrow \cdots \rightarrow v_5 \rightarrow v_7 \]

    4) کوتاهترین مسیر از گره شماره‌ی 4 به گره شماره‌ی 5 یال مستقیم آنها است (درایه‌ی $P_{45}$).

\[v_1 \rightarrow \cdots  \rightarrow v_4 \rightarrow v_5 \rightarrow v_7 \]

    5) کوتاهترین مسیر از گره شماره‌ی 1 به گره شماره‌ی 4 یال مستقیم آنها است (درایه‌ی $P_{14}$).

\[v_1  \rightarrow v_4 \rightarrow v_5 \rightarrow v_7 \]

    به این ترتیب مسیر بهینه با اندازه‌ی 7 (درایه‌ی $D_{17}$) مشخص شد.

\[v_1  \xrightarrow{4} v_4 \xrightarrow{2} v_5 \xrightarrow{1} v_7 \]

    الگوریتم فلوید-وارشال برای هر گراف با وزن‌های نامنفی همواره درست عمل می‌کند. اگر گراف وزن منفی نیز داشته ولی دور منفی نداشته باشد، باز هم عملکرد درستی خواهد داشت. به عنوان مثال، اگر در گراف فوق $M_{12} = -1$ بود، نتایج به این ترتیب می‌شد:

\[M = \begin{pmatrix} 0 & -1 & 2 & 4 & \infty & \infty & \infty & \infty  \\ \infty & 0 & \infty & \infty & \infty & \infty & 9 & 9  \\ 2 & \infty & 0 & 3 & \infty & \infty & \infty & \infty  \\ \infty & \infty & \infty & 0 & 2 & \infty & 4 & \infty  \\ \infty & \infty & \infty & \infty & 0 & \infty & 1 & \infty  \\ \infty & \infty & \infty & \infty & 6 & 0 & \infty & \infty  \\ 7 & 8 & \infty & \infty & 1 & 7 & 0 & 2  \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & 0 \end{pmatrix}\]

\[D = \begin{pmatrix} 0 & -1 & 2 & 4 & 6 & 14 & 7 & 8  \\ 16 & 0 & 18 & 20 & 10 & 16 & 9 & 9  \\ 2 & 1 & 0 & 3 & 5 & 13 & 6 & 8  \\ 10 & 9 & 12 & 0 & 2 & 10 & 3 & 5  \\ 8 & 7 & 10 & 12 & 0 & 8 & 1 & 3  \\ 14 & 13 & 16 & 18 & 6 & 0 & 7 & 9  \\ 7 & 6 & 9 & 11 & 1 & 7 & 0 & 2  \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & 0 \end{pmatrix} \qquad P = \begin{pmatrix} 0 & 0 & 0 & 0 & 4 & 7 & 5 & 2  \\ 7 & 0 & 7 & 7 & 7 & 7 & 0 & 0  \\ 0 & 1 & 0 & 0 & 4 & 7 & 5 & 7  \\ 7 & 7 & 7 & 0 & 0 & 7 & 5 & 7  \\ 7 & 7 & 7 & 7 & 0 & 7 & 0 & 7  \\ 7 & 7 & 7 & 7 & 0 & 0 & 5 & 7  \\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0  \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}\]

    اگر گراف دور منفی داشته باشد، الگوریتم خروجی درستی نخواهد داشت. به عنوان مثال، اگر در گراف فوق $M_{27} = -9$ بود، نتایج زیر حاصل می‌شد:

\[M = \begin{pmatrix} 0 & 1 & 2 & 4 & \infty & \infty & \infty & \infty  \\ \infty & 0 & \infty & \infty & \infty & \infty & -9 & 9  \\ 2 & \infty & 0 & 3 & \infty & \infty & \infty & \infty  \\ \infty & \infty & \infty & 0 & 2 & \infty & 4 & \infty  \\ \infty & \infty & \infty & \infty & 0 & \infty & 1 & \infty  \\ \infty & \infty & \infty & \infty & 6 & 0 & \infty & \infty  \\ 7 & 8 & \infty & \infty & 1 & 7 & 0 & 2  \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & 0 \end{pmatrix}\]

\[D = \begin{pmatrix} -1 & 0 & 1 & 3 & -7 & -1 & -9 & -6  \\ -2 & -1 & 0 & 2 & -8 & -2 & -10 & -7  \\ 1 & 2 & 0 & 3 & -5 & 1 & -7 & -4  \\ 10 & 11 & 12 & 0 & 2 & 10 & 2 & 5  \\ 8 & 9 & 10 & 12 & 0 & 8 & 0 & 3  \\ 14 & 15 & 16 & 18 & 6 & 0 & 6 & 9  \\ 6 & 7 & 8 & 10 & 0 & 6 & -2 & 1  \\ \infty & \infty & \infty & \infty & \infty & \infty & \infty & 0 \end{pmatrix} \qquad P = \begin{pmatrix} 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7  \\ 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7  \\ 7 & 7 & 0 & 0 & 7 & 7 & 7 & 7  \\ 7 & 7 & 7 & 0 & 0 & 7 & 7 & 7  \\ 7 & 7 & 7 & 7 & 0 & 7 & 7 & 7  \\ 7 & 7 & 7 & 7 & 0 & 0 & 7 & 7  \\ 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7  \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}\]

    تفاوت اصلی این خروجی با خروجی قبلی در اعداد منفی قطر اصلی ماتریس $D$ است. گره‌هایی که اعداد متناظر قطر اصلی آنها (در اینجا $ \{ v_1,v_2,v_7 \}$) منفی باشند، گرهی از یک مسیر با وزن منفی هستند. از این نکته برای تشخیص وجود دور منفی در گراف توسط الگوریتم فلوید-وارشال استفاده می‌شود.

    تذکر: در گراف‌های بدون جهت وجود یال منفی به معنی وجود دور منفی نیز هست (چرا؟).

      

پیاده‌سازی الگوریتم فلوید-وارشال

  [بازگشت به فهرست]

تابع Floyd_Warshall یک پیاده‌سازی ساده از الگوریتم فلوید-وارشال به زبان برنامه‌نویسی ++C است که با دریافت ماتریس مجاورت graph، اندازه‌ی کوتاهترین مسیر بین گره‌های آن را در ماتریس D تولید می‌کند.

      

void Floyd_Warshal(int graph[MAX][MAX], int D[MAX][MAX], int P[MAX][MAX], int numberOfNodes){
  for(int i = 0 ; i < numberOfNodes ; i++)
    for(int j = 0 ; j < numberOfNodes ; j++){
      D[i][j] = graph[i][j];
      P[i][j] = -1;
    }
  for(int k = 0 ; k < numberOfNodes ; k++)
    for(int i = 0 ; i < numberOfNodes ; i++)
      for(int j = 0 ; j < numberOfNodes ; j++)
10         if(D[i][j] > D[i][k] + D[k][j]){
11           D[i][j] = D[i][k] + D[k][j];
12           P[i][j] = k;
13         }
14 }

      

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

    تکرار حلقه‌ی بیرونی (با شمارنده‌ی k) ماتریس‌های $D^{(k)}$ را تولید می‌کند. در ساخت ماتریس $ D^{(k)} $ از روی ماتریس $ D^{(k-1)} $ درایه‌های سطر و ستون $k$ بدون تغییر باقی مانده (چرا؟) و سایر درایه‌ها نیز در صورت تغییر از همین درایه‌ها ساخته می‌شوند. به این ترتیب نوشتن درایه‌های ماتریس جدید روی محل حافظه‌ی ماتریس قبلی اشکالی در محاسبات پیش نمی‌آورد. همچنین درایه‌های ماتریس P به جای صفر با $-1$ مقداردهی اولیه شده است (چرا؟).

      

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

  [بازگشت به فهرست]

بر اساس کد ارائه شده، پیاده‌سازی الگوریتم فلوید-وارشال از سه حلقه‌ی تکرار تو در تو تشکیل یافته است که هر کدام $n$ بار تکرار می‌شوند. بنابراین مرتبه‌ی زمانی اجرای این الگوریتم برای گرافی با $n$ گره $\theta (n^3) $ است.


این نوشته آخرین بار در تاریخ سه‌شنبه، ۵ مرداد ماه ۱۳۹۵ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
        ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
        آشنایی با الگوریتم دایکسترا برای یافتن کوتاهترین مسیر تک‌مبدأ در گراف وزن‌دار بدون یال منفی با قطعه کد به زبان ++C
        بررسی مسئله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016 سایت تهران
        بررسی مسئله‌ی بشکه‌های آب (Water Barrels)، از سوالات مسابقات برنامه‌نویسی بیان
        بررسی مسئله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی موجود در کتاب Programming Challenges و وبسایت UVa Online Judge
        بررسی مسئله‌ی تاریخچه‌ی جدول (Grid History)، از سوالات مسابقات برنامه‌نویسی بیان
        بررسی الگوریتم‌های محاسبه‌ی دنباله‌ی اعداد فیبوناچی و کارایی آنها
        بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه‌ی آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
        معرفی الگوریتم جستجوی اول عمق (DFS) برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C
        بررسی مسئله‌ی آسانسورها (Elevators)، از سوالات مسابقات برنامه‌نویسی ACM
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» جابر

سه‌شنبه، ۲۳ آذر ماه ۱۳۹۵، ساعت ۱۲:۱۷
زیاد اموزنده نبود