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

تخفیف برای خرید این پروژه: زیر دکمه خرید، در پایین همین صفحه

پیاده سازی

قیمت :   ۷۵۰۰ تومان ( هفت هزار و پانصد تومان)

رشته :

کامپیوتر

نوع فایل:

CPP , EXE

توضیحات:


توضیحات :

پیاده سازی Floyd با پلاس

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

الگوریتم وارشال همهٔ مسیرهای ممکن در یک گراف، بین هر جفت از راس هارا مقایسه می‌کند. این الگوریتم قادر است این کار را تنها با V^3 مقایسه انجام دهد. این ملاحظه قابل توجهی می‌باشد که در یک گراف V^2 یال وجود داشته باشد وهر ترکیبی از یالها چک شده باشد. یک گراف G با راس‌های Vi که 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

== تصویری از محیط  فایل اجرایی این پروژه : 

floyed

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

 


مشاهده بخشهایی از سورس کد این پروژه :

#include”iostream.h”
#include”conio.h”
#include”stdlib.h”
#include”math.h”
#include”graphics.h”

#define MAX 20 //Maximum number of nodes

int h=315,v=238,i,j,x,y,z,s,d,t,n,spath=10000;
struct linkdata
{
int presence; //Indicates presence or absence of link
int length; //Indicates length of link in kms, if present
};
struct coords
{
int m; //X coordinate
int n; //Y coordinate
};
linkdata subnet[MAX][MAX]; //Array holding subnet map
int node[MAX],nodef[MAX]; //Arrays holding list of intermediate nodes
int number[MAX]; //Array holding pointers to contents of int. node arrays
coords points[MAX]; //Array holding X,Y coordinates of graph circles
char names[5]; //Array holding numbers for display in ‘char’ format

void main()
{
//Initialization section
//———–

//Initialize graphics
int gdriver=9,gmode=2;
initgraph(&gdriver,&gmode,”\\tc\\bgi”);
cleardevice();

//Welcome message
cout<<“\n\nShortest Path )”;

//Reset subnet array
for(i=0;i<15;i++)
for(j=0;j<15;j++)
{
subnet[i][j].presence=0;
subnet[i][j].length=10000;
}

//Data entry section
//————-

//Ask user to enter the subnet details
cout<<“\n\nPlease enter the details …”;

//Enter total number of nodes in subnet; maximum 20
cout<<“\n\nEnter the total number of nodes : “;
cin>>t;

//Form array map of subnet
for(i=0;i<t-1;i++)
{
cout<<“\nEnter the number of nodes to which node “<<i+1<<” is connected: “;
cin>>x;
cout<<“\nEnter the numbers of those nodes one by one:”;
for(j=0;j<x;j++)
{
cout<<“\n”<<j+1<<“: “;
cin>>y;
subnet[i][y-1].presence=subnet[y-1][i].presence=1;
cout<<“\nEnter length of link from “<<i+1<<” to “<<y<<” : “;
cin>>z;
subnet[i][y-1].length=subnet[y-1][i].length=z;
}
}

//Enter source & destination node
cout<<“\nEnter the source node number: “;
cin>>s;
cout<<“\nEnter the destination node number: “;
cin>>d;

//Transfer list of nodes (all except source & destination) to a new array
j=0;
for(i=1;i<=t;i++)
if((i!=s)&&(i!=d))
{
node[j]=i-1;
j++;
};

//Shortest path calculation process begins
//—————–
cout<<“\nProcessing…”;
n=0;
z=0;

//Check if a direct link is available; if yes, display directly
if(subnet[s-1][d-1].presence==1)
{spath=subnet[s-1][d-1].length;
goto end;
}

//Else try to find a valid route with intermediate nodes
do
{
n++;

//Reset intermediate node number pointer array
for(i=0;i<n;i++)
number[i]=0;

do
{
//Check if intermediate nodes are being repeated in ‘number[]’ array
x=0;
if (n>1)
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(number[i]==number[j])
{
x=1;
goto ok;
}
ok:

if((subnet[s-1][node[number[0]]].presence==1)&&(subnet[node[number[n-1]]][d-1].presence==1)&&(x==0))
{
x=0;
y=0;
y=subnet[s-1][node[number[0]]].length+subnet[node[number[n-1]]][d-1].length;
if((n-1)>0)
{
j=0;
do
{
if(subnet[node[number[j]]][node[number[j+1]]].presence==0) x=1;
else y=y+subnet[node[number[j]]][node[number[j+1]]].length;
j++;
}
while((j<n-1)&&(x==0));
}
if((x==0)&&(y<spath))
{
spath=y;
for(i=0;i<n;i++) nodef[i]=node[number[i]];
}
}
x=1;
y=0;
z=0;

//Check if all options with current ‘n’ are exhausted
for(i=0;i<n;i++)
if(number[i]<t-3) z=1;

do
{
if((number[n-x])<(t-3))
{
number[n-x]++;
y=1;
}
else
{
number[n-x]=0;
x++;
}
}
while((x<=n)&&(y==0));
}
while(z==1);
}
while((n<t-2)&&(spath==10000));

 

دانلود کامل پروژه همراه با فایل سورس کد و فایل اجرایی آن
در تمامی ساعات شبانه روز >> پرداخت آنلاین و دانلود آنلاین پروژه

پذیرش و انجام سفارشات پروژه های شما
شماره تماس پشتیبانی سایت : ۰۹۳۹۲۷۶۱۶۳۰

تخفیف بسیار ویژه ۳۰ درصدی : دوست عزیز سعی ما این بوده که پروژه ها را با کمترین قیمت ممکن (مقایسه کنید با قیمت سایر سایتها) در اختیار شما قرار دهیم اما اگر دوستی هست که واقعا این مبلغ نیز برایش مقدور نیست می توانید عنوان تحقیق یا پروژه مورد نظر، کلمه Takhfif و آدرس ایمیل خود را به شماره پشتیبانی سایت  ۰۹۳۹۲۷۶۱۶۳۰  پیامک کنید تا لینک تخفیف سریعا برای شما ارسال گردد .

خرید انواع تحقیق و پروژه های شما بصورت توافقی : ۰۹۳۹۲۷۶۱۶۳۰

Related posts

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

Translate »