ماتریس مجاورت با یال منفی

[gm.sara]

سلام
یه سئوالی که برای من پیش آمد اینه که در گراف با یال دارای وزن میشه که وزن یال عددی منفی باشد ؟!

به هر حال بگید اگر وزن یالی منفی بود چه کار باید کرد ؟

ممنون می شم .

[raha_hakhamanesh]

با سلام
به اطلاع شما می رسونم البته می تواند یالهای یک گراف منفی باشد ولی شما نگفتید دقیقا چه کار می خواهید بکنید اما توجه کنید در اینصورت برخی محاسبات تغییر می کند مثلا جستجوی کوتاهترین مسیر در یک گراف که می شه با الگوریتم دیکسترا اون رو بدست آورد دیگه در حالتی که گراف دارای یال منفی باشه درست عمل نمی کنه و بایستی از یک الگوریتم دیگه(در این مورد مثلاً الگوریتم فلوید وارشال) استفاده شود . بهر حال یال می تواند منفی باشد و با توجه به سوال ممکن است راه حل تفاوت کند

[gm.sara]

با تشکر از شما دوست محترم

خوب مثلا همین الگوریتم فلوید را چه تغییری می شه داد که گراف با وزن منفی را محاسبه کنه ؟

[raha_hakhamanesh]

با سلام
الگوریتم فلوید وارشال برای گراف با یال منفی است و وجود یال منفی را تشخیص می دهد ولی اگر دارای دور منفی باشد آنگاه آن را تشخیص می دهد اما گزارش نمی کند .
الگوریتم بلمن-فورد گراف با یال منفی را می پذیرد و چنانچه در گراف دچار دور منفی شویم آن را گزارش می دهد.
الگوریتم جانسون گراف با یال منفی را می پذیرد و دور منفی را نیز گزارش می کند . اما بطور مجانبی سریعتر از فلوید-وارشال است .
اما توجه کنید همه این الگوریتم ها کار جستجو در گراف را انجام می دهند و هدف پیدا کردن کوتاهترین مسیر است اما باید بر اساس تعریف مسئله و نیاز هر یک از آنها را انتخاب کنید چون مرتبه زمانی آنها معمولا بیشتر از n pow(2) است تقریبا نزدیک 3 یعنی برای 100 نقطه (که در مقیاس کاربردی خیلی کم است) تقریبا 1000000 عملیات نیاز است . بنابراین به مرتبه زمانی هریک از الگوریتم های فوق توجه کنید
موفق باشید

[shima and pariya]

من برنامشو دارم واسم توضیح میدی لطفا


#include<iostream.h>
#include<conio.h>

class bellford
{
int size,**node,**metric,**ans,count,*temp;
int i,j,k,start_node,pass;

public:
bellford()
{
pass=count=i=j=0;
}

void accept(); // Accepts Number Of Nodes
void create(); // Creates Connection and Metric Matrices
void start(); // Accepts starting node for comm.
void bf(); // Generates Path for Routing
//void make_ans(int,int); // Holds Answers
void oracle(); // Displays Final Answer
};

void bellford::accept()
{
cout<<"Enter size of Matrix:";
cin>>size;
create();
}

void bellford::create()
{
node=new int*[size];
for(i=0;i<size;i++)
node[i]=new int[size];

metric=new int*[size];
for(i=0;i<size;i++)
metric[i]=new int[size];

/*ans=new int*[size];
for(i=0;i<size;i++)
ans[i]=new int[size];

for(i=0;i<size;i++)
{
//ans[i][0]=i+1;
for(j=0;j<size;j++)
{
ans[i][j]=0;
}
}
*/
clrscr();
cout<<"Enter Connection Between Nodes"<<endl<<endl;
cout<<"0:Connection Absent\n1: Connection Present"<<endl<<endl;

for(i=0;i<size;i++)
{
for(j=0;j<size;j++)
{
if(i==j)
{
node[i][j]=0;
}
else
{
cout<<"Node "<< i+1 <<" -> Node "<<j+1<<": ";
cin>>node[i][j];
cout<<endl;
if(node[i][j]==1)
{
cout<<endl<<"Enter Metric for Node "<< i+1 <<" -> Node "<<j+1<<": ";
cin>>metric[i][j];
cout<<endl;
}
}
}
}
start();
}

void bellford::start()
{
cout<<endl<<"Enter The Starting Node: ";
cin>>start_node;
//cout<<endl;
j=0;
//pass=0;
temp=new int[size];
for(i=0;i<size;i++) // No. of nodes start_node is conn. to
{
if(node[start_node-1][i]==1)
{
temp[j++]=i+1;
cout<<"Temp:"<<j-1<<" : "<<temp[j-1]<<endl;
count++;
}
}
ans=new int*[count]; // No. of rows present in the ans matrix
// Eg.
// 0________
// 1________
// 2________
for(j=0;j<size;j++) // Puttin size of each row as size of full matrix
{ // Eg.
ans[j]=new int[size];// 5-> _ _ _ _ _
} // 5-> _ _ _ _ _
// 5-> _ _ _ _ _
i=0;//Making i=0 to put values of start_node in every row
j=0;
while(i<count)
{
ans[i][0]=start_node;// Eg. 1 _ _ _ _ _
ans[i++][1]=temp[j++];
}

/*for(i=0;i<count;i++) // For temporary chking of values in ans
{
for(j=0;j<size;j++)
{
cout<<i+1<<":"<<j+1<<":"<<ans[i][j]<<endl;
}
cout<<endl;
}*/

pass=1; // We r at pos 0 1 _ _ _ in ans matrix
bf();
}

void bellford::bf()
{
i=0; // Making i=0 to put values of start_node in every row
j=0;
while(i<count)
{
for(j=0;j<size;j++)
{
if(node[ans[i][pass]-1][j]==1)
ans[i][pass+1]=node[ans[i][pass]-1][j]+1;
}
i++;
pass++;
}
}

/*void bellford::make_ans(int x,int y)
{

ans[x][y]=y;
//pass++;
}*/

void bellford::oracle()
{
for(i=0;i<count;i++)
{
for(j=0;j<size;j++)
{
cout<<i+1<<":"<<j+1<<":"<<ans[i][j]<<endl;
}
cout<<endl;
}
}

int main()
{
bellford b;
clrscr();
b.accept();
getch();
b.oracle();
getch();
return 1;
}

[soroushp]

سلام
یه سئوالی که برای من پیش آمد اینه که در گراف با یال دارای وزن میشه که وزن یال عددی منفی باشد ؟!

به هر حال بگید اگر وزن یالی منفی بود چه کار باید کرد ؟

ممنون می شم .

الان یال منفی به صورت منطقی به چه معناست؟ ما تو ماتریس مجاورت یا 0، بی نهایت و یا وزن یال رو می زاریم ، وزن منفی که تو دایجکسترا مطرح شده به چه معناست؟؟؟