ورود به حساب ثبت نام جدید فراموشی کلمه عبور
برای ورود به حساب کاربری خود، نام کاربری و کلمه عبورتان را در زیر وارد کرده و روی “ ورود به حساب” کلیک کنید.





اگر فرم ثبت نام برای شما نمایش داده نمیشود، اینجا را کلیک کنید.









اگر فرم بازیابی کلمه عبور برای شما نمایش داده نمیشود، اینجا را کلیک کنید.





نمایش نتایج: از 1 به 1 از 1
  1. #1
    sina
    sina
    Guest

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

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


    کد:
    #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;
    }
  2. 1
نمایش نتایج: از 1 به 1 از 1

اطلاعات موضوع

کاربرانی که در حال مشاهده این موضوع هستند

در حال حاضر 1 کاربر در حال مشاهده این موضوع است. (0 کاربران و 1 مهمان ها)

موضوعات مشابه

  1. پاسخ: 1
    آخرين نوشته: 2013-06-08, 12:39 PM
  2. سورس کار با دیتا بیس
    توسط vahid4251 در انجمن VB.NET
    پاسخ: 0
    آخرين نوشته: 2012-12-15, 11:56 PM
  3. مشکل در لاگین به دیتا بیس sql
    توسط mehraaaaan در انجمن #C
    پاسخ: 2
    آخرين نوشته: 2012-10-25, 06:50 PM
  4. چگونگی ذخیره سایت در دیتا بیس
    توسط ali11 در انجمن ASP.NET
    پاسخ: 0
    آخرين نوشته: 2012-08-10, 12:43 AM
  5. چگونگی ذخیره سایت در دیتا بیس
    توسط ali11 در انجمن #C
    پاسخ: 0
    آخرين نوشته: 2012-08-10, 12:39 AM

کلمات کلیدی این موضوع

مجوز های ارسال و ویرایش

  • شما نمیتوانید موضوع جدیدی ارسال کنید
  • شما امکان ارسال پاسخ را ندارید
  • شما نمیتوانید فایل پیوست کنید.
  • شما نمیتوانید پست های خود را ویرایش کنید
  •  

Content Relevant URLs by vBSEO 3.6.0 RC 2