فروش پروژه الگوریتم فلوید به زبان #C

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

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

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

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

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

    فرض کنید ماتریس مجاورت گراف را با Mn×n و گره‌های گراف را به صورت {v1,v2,v3,⋯,vn} نمایش دهیم. اگر ماتریس D(k)n×n معرف ماتریس طول کوتاهترین مسیر بین گره‌های گراف تنها با اجازه‌ی عبور از گره‌های {v1,v2,v3,⋯,vk} باشد، ماتریس D(n) جواب مسأله خواهد بود. همچین D(0) همان M است (چرا؟). پس محاسبه‌ی کوتاهترین مسیر بین گره‌ها به محاسبه‌ی ماتریس D(n) تبدیل می‌شود.

    کوتاهترین مسیر از گره vi به گره vj با اجازه‌ی عبور از گره v1 یا مسیر مستقیم بین آن دو (با اندازه‌ی Mij) است یا مسیری که از گره v1 (با اندازه‌ی Mi1+M1j) می‌گذرد؛ یعنی:

D(1)ij=min{Mij,Mi1+M1j}

    با استفاده از این رابطه درایه‌های ماتریس D(1) از روی ماتریس مجاورت (یا همان ماتریس D(0)) قابل محاسبه است. درایه‌های ماتریس D(2) طول کوتاهترین مسیرها با اجازه‌ی عبور از گره‌های v1 و v2 است. چنین مسیرهایی یا بدون استفاده از گره v2 هستند (یعنی همان D(1)ij) یا با عبور از این گره. اگر از این گره استفاده شود، طول کوتاهترین مسیر D(1)i2+D(1)2j خواهد بود؛ چرا که D(1)i2 طول کوتاهترین مسیر از گره vi به این گره و D(1)2j طول کوتاهترین مسیر از آن به گره vj است؛ پس:

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};0<k≤n,D(0)=M

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

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

الگوریتم بحث شده تنها برای محاسبه‌ی اندازه‌ی کوتاهترین مسیر بین گره‌های گراف بوده و امکان تشخیص گره‌های این مسیر را ندارد. برای رفع این مشکل از ماتریس Pn×n استفاده می‌شود که در ابتدا همه‌ی عناصر آن صفر است. طی محاسبات ماتریس‌های D(k) اگر گره k در کوتاهترین مسیر بین دو گره i و j انتخاب شد مقدار k در Pij قرار داده می‌شود. به این ترتیب در انتهای الگوریتم یک شماره‌ی گره واسط بین دو گره i و j در درایه‌ی Pij موجود است. این درایه تنها در شرایطی صفر خواهد ماند که یا مسیری بین دو گره وجود نداشته، یا کوتاهترین مسیر یال مستقیم بین آن دو باشد. با مشخص شدن این گره واسط، تشخیص مسیر بهینه از مبدأ به مقصد تبدیل به تشخیص مسیر بهینه از مبدأ به این گره و از این گره به مقصد می‌گردد. تشخیص چنین مسیرهایی نیز از طریق همین ماتریس به صورت بازگشتی انجام می‌گیرد. به عنوان مثال برای گراف زیر:

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

M=(0124∞∞∞∞∞0∞∞∞∞992∞03∞∞∞∞∞∞∞02∞4∞∞∞∞∞0∞1∞∞∞∞∞60∞∞78∞∞1702∞∞∞∞∞∞∞0)

D=(01246147916018201016992303513681011120210358910120813141516186079789111702∞∞∞∞∞∞∞0)P=(0000475770777700010047577770075777770707777700570011000000000000)

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

    1) کوتاهترین مسیر از گره شماره‌ی 1 به گره شماره‌ی 7 از گره شماره‌ی 5 (درایه‌ی P17) عبور می‌کند.

v1→⋯→v5→⋯→v7

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

v1→⋯→v5→v7

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

v1→⋯→v4→⋯→v5→v7

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

v1→⋯→v4→v5→v7

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

v1→v4→v5→v7

    به این ترتیب مسیر بهینه با اندازه‌ی 7 (درایه‌ی D17) مشخص شد.

v14→v42→v51→v7

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

M=(0−124∞∞∞∞∞0∞∞∞∞992∞03∞∞∞∞∞∞∞02∞4∞∞∞∞∞0∞1∞∞∞∞∞60∞∞78∞∞1702∞∞∞∞∞∞∞0)

D=(0−124614781601820101699210351368109120210358710120813141316186079769111702∞∞∞∞∞∞∞0)P=(0000475270777700010047577770075777770707777700570111000000000000)

    اگر گراف دور منفی داشته باشد، الگوریتم خروجی درستی نخواهد داشت. به عنوان مثال، اگر در گراف فوق M27=−9 بود، نتایج زیر حاصل می‌شد:

M=(0124∞∞∞∞∞0∞∞∞∞−992∞03∞∞∞∞∞∞∞02∞4∞∞∞∞∞0∞1∞∞∞∞∞60∞∞78∞∞1702∞∞∞∞∞∞∞0)

D=(−1013−7−1−9−6−2−102−8−2−10−71203−51−7−410111202102589101208031415161860696781006−21∞∞∞∞∞∞∞0)P=(7777777777777777770077777770077777770777777700777777777700000000)

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

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

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

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

1  void Floyd_Warshal(int graph[MAX][MAX], int D[MAX][MAX], int P[MAX][MAX], int numberOfNodes){
2    for(int i = 0 ; i < numberOfNodes ; i++)
3      for(int j = 0 ; j < numberOfNodes ; j++){
4        D[i][j] = graph[i][j];
5        P[i][j] = -1;
6      }
7    for(int k = 0 ; k < numberOfNodes ; k++)
8      for(int i = 0 ; i < numberOfNodes ; i++)
9        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 گره θ(n3) است.