سورس پیدا کردن کوتاه ترین مسیر با الگوریتم فلوید به زبان C++

پنجشنبه ۱ اسفند ۱۳۹۸
بازدید ۲,۶۰۱ نفر
سعید سیفی زاده
(25 امتیاز از 5 رای)
Loading...

تصویر cpp-program-to-find-shortest-path-using-floyd-algorithm_8177 سورس پیدا کردن کوتاه ترین مسیر با الگوریتم فلوید به زبان C++

سورس پیدا کردن کوتاه ترین مسیر با الگوریتم فلوید به زبان C++

در این بخش سورس پیدا کردن کوتاه ترین مسیر با الگوریتم فلوید به زبان C++ را برای شما آماده کرده ایم که در محیط نرم افزار Code::Blocks و زبان برنامه نویسی سی پلاس پلاس نوشته شده است. در ادامه می توانید توضیحات، تصاویر و همچنین فیلمی از نحوه اجرا شدن پروژه را مشاهده کنید.

توضیحات پروژه

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

الگوریتم فلوید- وارشال (Floyd-Warshall)، یک الگوریتم تحلیل گراف برای پیدا کردن کوتاه ترین مسیر در یک گراف جهت دار و وزن دار است که توسط دو دانشمند آمریکایی به نام های استفن وارشال و رابرت فلوید ساخته شده است. با یک بار اجرای یک الگوریتم کوتاه ترین مسیر بین همه جفت راس ها پیدا خواهد شد.

قسمت های از سورس کد

#include<iostream>
#include<conio.h>
using namespace std;
//*****************************
const int COUNTYAL = 3;    //tehdad yalha dar har node
const int N = 4;      // tehdad nodha
class  graph        // tahrif class graph
{
  private:
	  struct info                         // sakhtar har node
	  {                                   //
		int id;                            //shomare node
		struct info *yal[COUNTYAL];         //tahrif yalha dar node
		struct info *link;                  //tahrif link baray vasl be node bahdi
		int vaznyal[COUNTYAL];              //tahrif vazne har yal
		int kharabi[COUNTYAL];              // tahrif kharabi har yal
	  };
	 typedef struct info node;              // tahrif dade az nohe sakhtar balay
	 node *first,*gofront;                 //  tahrif  2 esharegar baray ebteda va entehay list
	 int b[N][N];                           //tahrif matrix baraye pida kardane masir kotah

    //-------------------------------------
	 int iskharab(int idnode,int idyal)   // tabe test kharabi yal
	 {
		node *temp=getnode(idnode);
	  if(temp != NULL)
		 return temp->kharabi[idyal];
	  return 1;
	 }
	 //-------------------------------------
	 int getvazn(int idnode,int idyal)   // tabe gereftane vazn yal
	 {
		node *temp=getnode(idnode);
	  if(temp != NULL)
		 return temp->vaznyal[idyal];
	  return 0;
	 }
  public:
	 graph()       // sazande kellass baraye megdar dehi avvalie be dadaha
	 {
	  int i,j;
	  first = NULL;
	  gofront = NULL;
	  for(i=0;i<N;i++)
		for(j=0;j<N;j++)
		  b[i][j]=0;
	 }
 
	 //-------------------------------------
	 int getshortpath(int idnode1,int idnode2) // tabe pida kardane kotahtarin masir az node mabdah ta node magsad
	 {
	  int i,j;
	  graphtomatrix();
	  floyds();
     return b[idnode1][idnode2];
	 }
};
//----------------------------------------------------------------------------
int main()
{
  graph graph1;      // graph1 az nohe class graph tahrif mishe
  int idnode1,idyal,vazn,kharab,idnode2;
  for (int i = 0; i < N; i++)     // ye halge ke node ha ro be sorate automatic eijad mikone  be tedad N=4
	 graph1.addnode(i);
  while(1)     // halge binahayat
	 {
	  cout<<"enter id node1:";     // cin ha baraye gereftane atelahat nodaha ast
	  cin>>idnode1;
	  cout<<"enter id node2:";
	  cin>>idnode2;
	  cout<<"enter id yal:";
	  cin>>idyal;
	  cout<<"enter vazn yal:";
	  cin>>vazn;
	  cout<<"enter kharabi:";
	  cin>>kharab;
	  graph1.addvazn(idnode1,idyal,vazn,kharab,idnode2);   //  ezafe kardane etelahate bala be list
	  cout<<"Press Esc End OR Any Key Continue ..."<<endl;
	  if(getch() == 27) break;               // age esc ro bezani dige node ezafe nemikone
	 }
  cout<<"Find ShortPath Betwen 2 Node."<<endl;
  cout<<"enter id node1:";
  cin>>idnode1;
  cout<<"enter id node2:";
  cin>>idnode2;
  cout<<"ShortPath Betwen Node "<<idnode1<<" To "<<idnode2<<" = "<<graph1.getshortpath(idnode1,idnode2);// pida kardane kotahtarin masir bine idnode1 va idnode2
  getch();
}

#include<iostream>

#include<conio.h>

using namespace std;

//*****************************

const int COUNTYAL = 3; //tehdad yalha dar har node

const int N = 4; // tehdad nodha

class graph // tahrif class graph

{

private:

struct info // sakhtar har node

{ //

int id; //shomare node

struct info *yal[COUNTYAL]; //tahrif yalha dar node

struct info *link; //tahrif link baray vasl be node bahdi

int vaznyal[COUNTYAL]; //tahrif vazne har yal

int kharabi[COUNTYAL]; // tahrif kharabi har yal

};

typedef struct info node; // tahrif dade az nohe sakhtar balay

node *first,*gofront; // tahrif 2 esharegar baray ebteda va entehay list

int b[N][N]; //tahrif matrix baraye pida kardane masir kotah

//-------------------------------------

int iskharab(int idnode,int idyal) // tabe test kharabi yal

{

node *temp=getnode(idnode);

if(temp != NULL)

return temp->kharabi[idyal];

return 1;

}

//-------------------------------------

int getvazn(int idnode,int idyal) // tabe gereftane vazn yal

{

node *temp=getnode(idnode);

if(temp != NULL)

return temp->vaznyal[idyal];

return 0;

}

public:

graph() // sazande kellass baraye megdar dehi avvalie be dadaha

{

int i,j;

first = NULL;

gofront = NULL;

for(i=0;i<N;i++)

for(j=0;j<N;j++)

b[i][j]=0;

}

//-------------------------------------

int getshortpath(int idnode1,int idnode2) // tabe pida kardane kotahtarin masir az node mabdah ta node magsad

{

int i,j;

graphtomatrix();

floyds();

return b[idnode1][idnode2];

}

};

//----------------------------------------------------------------------------

int main()

{

graph graph1; // graph1 az nohe class graph tahrif mishe

int idnode1,idyal,vazn,kharab,idnode2;

for (int i = 0; i < N; i++) // ye halge ke node ha ro be sorate automatic eijad mikone be tedad N=4

graph1.addnode(i);

while(1) // halge binahayat

{

cout<<"enter id node1:"; // cin ha baraye gereftane atelahat nodaha ast

cin>>idnode1;

cout<<"enter id node2:";

cin>>idnode2;

cout<<"enter id yal:";

cin>>idyal;

cout<<"enter vazn yal:";

cin>>vazn;

cout<<"enter kharabi:";

cin>>kharab;

graph1.addvazn(idnode1,idyal,vazn,kharab,idnode2); // ezafe kardane etelahate bala be list

cout<<"Press Esc End OR Any Key Continue ..."<<endl;

if(getch() == 27) break; // age esc ro bezani dige node ezafe nemikone

}

cout<<"Find ShortPath Betwen 2 Node."<<endl;

cout<<"enter id node1:";

cin>>idnode1;

cout<<"enter id node2:";

cin>>idnode2;

cout<<"ShortPath Betwen Node "<<idnode1<<" To "<<idnode2<<" = "<<graph1.getshortpath(idnode1,idnode2);// pida kardane kotahtarin masir bine idnode1 va idnode2

getch();

}