پیاده سازی الگوریتم فلوید-وارشال با سی پلاس
|
||||||||||||
توضیحات : پیاده سازی الگوریتم فلوید Floyd با سی پلاس در علومکامپیوتر الگوریتم فلوید-وارشال یک الگوریتم تحلیل گراف برای پیدا کردن کوتاهترین مسیر در یگ گرافجهتدارو وزن دار میباشد .با یکبار اجرای این الگوریتم کوتاهترین مسیر بین همهٔ جفت راسها پیدا خواهد شد. الگوریتم فلوید-وارشال به نام استفن وارشال و روبرت فلوید نامگذاری شدهاست. این الگوریتم یک مثال از برنامه نویسی پویامیباشد. در این الگوریتم، ابتدا ماتریسمجاورت برای نقاط گراف نوشته شده و در مرحله ی بعد با استفاده از یک راس واسطه، کوتاه ترین فاصله بین نقاط را محاسبه کرده و ماتریس را با مقادیر جدید بازنویسی می کند. پس از آن دو نقطه به عنوان واسطه انتخاب شده و ماتریس جدید به دست می آید. با تکرار این روند الگوریتم به پایان رسیده و در نهایت ماتریسی ایجاد شده که کوتاه ترین مسیر بین تمامی نقاط را محاسبه کرده است. بدیهی است که کوتاه ترین مسیر بین مبدا و مقصد را می توان به راحتی از ماتریس تشکیل شده استخراج نمود. الگوریتم وارشال همهٔ مسیرهای ممکن در یک گراف، بین هر جفت از راس هارا مقایسه میکند. این الگوریتم قادر است این کار را تنها با مقایسه انجام دهد. این ملاحظه قابل توجهی میباشد که در یک گراف یال وجود داشته باشد وهر ترکیبی از یالها چک شده باشد. یک گراف با راسهای که i از ۱ تا N میباشد را در نظر بگیرید. علاوه بر این یک تابعبه نام (shortestPath(i,j،k را در نظر بگیرید که کوتاهترین مسیر ممکن از i تا j را با استفاده از راسهای ۱ تا k که به عنوان راسهای میانی در امتداد مسیر میباشند را بر میگرداند. هم اکنون این تابع داده شدهاست .هدف ما پیدا کردن کوتاهترین مسیر از هر i تا هر j تنها با استفاده از راسهای ۱ تا ۱+k میباشد. دو کاندیدا برای این مسیر وجود دارد : ۱-کوتاهترین مسیری که فقط از راسهای موجود در مجموعه ی(k,……..,1) استفاده میکند. ۲-تعدادی مسیر که از i تا ۱+k و سپس از ۱+k تا j میروند وجود دارد که این مسیر بهتر میباشد. ما میدانیم که بهترین مسیر از i تا j که فقط از راسهای بین ۱ تا k+1 استفاده میکند توسط (ShortestPath(i,j،k تعریف شدهاست و واضح است که اگر یک مسیر بهتر از i تا۱+k و از ۱+k تا j وجود داشته باشد بنابراین طول مسیربین i,j ازالحاق کوتاهترین مسیر از i تا ۱+k و کوتاهترین مسیر از ۱+k تا j بدست میآید.بنابراین تابع ( ShortestPath(i,j،k را در در فرمول بازگشتی زیر ارائه میدهیم: این رابطه قلب الگوریتم وارشال میباشد این الگوریتم در اولین محاسبه ( ShortestPath(i,j،۱ را برای همهٔ جفتهای (i ,j) پیدا میکند و سپس از این برای پیدا کردن (Shortestpath(i,j،۲ برای همهٔ جفتهای (i ,j ) استفاده میشود و این روال تا زمانی که k=N شود ادامه مییابد و ما میتوانیم کوتاهترین مسیر بین جفتهای (i,j) رابا استفاده از راسهای میانی پیدا کنیم.
پیاده سازی الگوریتم فلوید Floyd با سی پلاس همراه با سورس کامل پروژه همراه با فایلهای EXE , CPP == تصویری از محیط فایل اجرایی این پروژه :
|
مشاهده بخشهایی از سورس کد این پروژه :
#include”iostream.h” #define MAX 20 //Maximum number of nodes int h=315,v=238,i,j,x,y,z,s,d,t,n,spath=10000; void main() //Initialize graphics //Welcome message //Reset subnet array //Data entry section //Ask user to enter the subnet details //Enter total number of nodes in subnet; maximum 20 //Form array map of subnet //Enter source & destination node //Transfer list of nodes (all except source & destination) to a new array //Shortest path calculation process begins //Check if a direct link is available; if yes, display directly //Else try to find a valid route with intermediate nodes //Reset intermediate node number pointer array do if((subnet[s-1][node[number[0]]].presence==1)&&(subnet[node[number[n-1]]][d-1].presence==1)&&(x==0)) //Check if all options with current ‘n’ are exhausted do |
دانلود کامل پروژه همراه با فایل سورس کد و فایل اجرایی آن
در تمامی ساعات شبانه روز >> پرداخت آنلاین و دانلود آنلاین پروژه
پذیرش و انجام سفارشات پروژه های شما
شماره تماس پشتیبانی سایت : ۰۹۳۹۲۷۶۱۶۳۰
توجه مهم :
*دوست عزیز در صورت نداشتن رمز پویا یا قطع بودن درگاه بانکی ، لطفا نام پروژه درخواستی خود را جهت هماهنگی برای دریافت شماره کارت واریزی و دریافت لینک دانلود، به واتساپ پشتیبانی سایت ۰۹۳۹۲۷۶۱۶۳۰ ارسال کنید *(از ساعت ۸ الی ۲۳)
دیدگاهتان را بنویسید