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

نمایش نتایج: از شماره 1 تا 4 از مجموع 4
Like Tree6نفر پسندیدند
  • 2 ارسال توسط Pouya
  • 3 ارسال توسط Hossein
  • 1 ارسال توسط siryahya

موضوع: الگوریتم دایجسترا ( بازگشتی ) c#

  1. #1
    ADMIN
    تاریخ عضویت
    2011 October
    محل سکونت
    گیلان
    سن
    30
    ارسال ها
    136
    تشکر
    814
    تشکر شده 480 بار در 131 پست


    1 امتياز مثبت از 1 راي
    آيا اين پست براي شما سودمند بود؟ بله | خیر

    الگوریتم دایجسترا ( بازگشتی ) c#


    Dijksta_Anim.gif

    الگوریتم دایجسترا


    در نظریه گراف، الگوریتم دایجسترا یکی از الگوریتم‌های پیمایش گراف است که توسط دانشمند هلندی علوم رایانه، اِدْسْخِر دَیْکْسْترا در سال ۱۹۵۹ ارایه شد.

    این الگوریتم یکی از الگوریتم‌های پیمایش گراف است که مسئلهٔ کوتاه‌ترین مسیر از مبدأ واحد را برای گراف‌های وزن‌داری که یال با وزن منفی ندارند، حل می‌کند و در نهایت با ایجاد درخت کوتاه‌ترین مسیر، کوتاه‌ترین مسیر از مبدأ به همهٔ رأس‌های گراف را به دست می‌دهد. همچنین می‌توان از این الگوریتم برای پیدا کردن کوتاه‌ترین مسیر از مبدأ تا رأس مقصد به این ترتیب بهره جست که در حین اجرای الگوریتم به محض پیداشدن کوتاه‌ترین مسیر از مبدأ به مقصد، الگوریتم را متوقف کرد.
    الگوریتم دایجسترا به نام کوتاه ترین مسیر تک منبع ( single Source shortest path ) نیز معروف است و مشابه الگوریتم پریم می باشد در صورتی که گراف یال با وزن منفی داشته باشد، این الگوریتم درست کار نمی‌کند و می‌بایست از الگوریتم‌های دیگر نظیر الگوریتم بلمن-فورد که پیچیدگی زمانی آنها بیشتر است استفاده کنیم.


    //In The Name Of God
    static void finder(int start, int end, double mweight, int[] way, int count)
    {
    count += 1;
    for (int i = 1; i <= p; i++)
    {
    if (weight[start, i] > 0 && weight[i, i] == 0)
    {
    if (i == end)
    {
    mweight += weight[start, i];
    way[count] = end;


    if (mweight < least)
    {
    least = mweight;
    for (int j = 0; j < 20; j++)
    bestway[j] = way[j];
    }
    mweight -= weight[start, i];
    continue;
    }
    mweight += weight[start, i];
    weight[start, start] = -1;
    way[count] = i;
    finder(i, end, mweight, way, count);
    way[count + 1] = 0;
    weight[start, start] = 0;
    mweight -= weight[start, i];
    }
    }
    }
    //خروجی این تابع آرایه ی BestWay است
    //که کوتاه ترین مسیر درون آن قرار میگیرد.



    سورس برنامه ی محاسبه و رسم کوتاه ترین مسیر الگوریتم دایجسترا روش بازگشتی پیوست شد...


    موضوعات مشابه:
    فایل های پیوست شده
    • نوع فایل: zip Dijkstra.zip (201.5 کیلو بایت,  این فایل 77 بار دانلود شده است)
    Tishab و pashekosh این را میپسندند


    ..::Never Trust Someone Who Lies To You , Never Lie To Someone Who Trusts You::..


  2. #2
    بنیانگذار
    تاریخ عضویت
    2010 January
    محل سکونت
    زیر سایه خدا
    سن
    37
    ارسال ها
    1,308
    تشکر
    2,923
    تشکر شده 2,205 بار در 886 پست
    نوشته های وبلاگ
    37


    4 امتياز مثبت از 4 راي
    آيا اين پست براي شما سودمند بود؟ بله | خیر
    این هم پیاده سازی ای هست که من در دوران دانشجوییم انجام دادم + توضیحاتی در مورد نحوه اجرا ,کارکرد و خروجی برنامه که تو وبلاگمون تو اون زمان دادم خدمت شما :

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


    حالا نحوه کار با برنامه . خیلی ها سوالشون این بود که چرا ما وقتی تعداد نودها رو وارد میکنیم به اندازه تعداد نود سطر داریم ؟ اصلا یعنی چی ؟
    تو شکل زیر توضیح دادم چرا . بینید وقتی شما گراف زیر رو میبینید . میبینید که مثلا b به a وصله و یک اندازه ای داره . بعد نود c هم به b وصله . خوب ما از این سطرها استفاده میکنیم تا اندازه هر نود نسبت به سایر نودها رو داشته باشیم که بعدا وقتی میخواییم کوتاهترین مسیر رو پیدا بکنیم بتونیم از این وزنها برای کارمون استفاده کنیم .چگونگی وارد کردن مقادیر هم مهم هست .
    مثلا تو شکل زیر گره 1 با خودش و گره های 2 و 3 مرتبطه اما با گره چهارم مرتبط نیست .
    تو خط اول میاییم اندازه ( یا فاصله ) این گرهها نسبت به گره 1 رو وارد میکنیم اینطوری
    node1 node2 node3 node4
    0 1 5 999

    999 هم یعنی بینهایت .
    خط دوم هم فاصله های سایر گر ها رو نسبت به گره 2میسنجیم
    node1 node2 node3 node4
    1 0 3 2

    اون صفری هم که میزاریم یعنی اینکه گره از خودش که فاصله ای نداره پس صفر میزاریم براش و همینطور الی اخر . تو شکل زیر اینو خیلی قشنگتر مشخص کردم .
    مثالی رو هم که میبینید خانم اهنگر لطف کردند برای تست برنامه ارائه دادن و شما میتونید خروجی برنامه رو بسنجید و ببینید که آیا برنامه درست جواب میده یا نه .
    خوب الان فکر کنم مشخص شد که چرا ما به تعداد نودها از کاربر سطر دریافت میکنیم و اندازه میگیریم .
    ----------------------
    در مور توضیحات هم فکر میکنم خیلی واضحه و اگه جایی مشکل دارید با دیباگر ویژوال استودیو خیلی راحت متوجه کار میشید اگر نشدید قبل از امتحان توضیح میدم ( یا اینکه کامنت بزارید مشکلتون رو مطرح کنید که اگه رسیدم حتما توضیح بدم ) .
    //بسم الله الرحمن الرحیم 
    //Dijkstra Algorithm implementation in C#
    //Seyyed Hossein Hasan Pour
    //Mazandaran University fo Science and Technology
    //June 11 2010

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace Dijkstra_Algorithm_in_Csharp
    {
    class Dijkstra_Algorithm_in_Csharp_Program
    {
    static int node_shoro = 0;
    static int[] Node_ghabli = new int[20];
    static void Main(string[] args)
    {
    Console.Write( "\t\t\t In the name of GOD");


    Console.Write("\n\t\t\t Dijkstra Algorithm In C[URL=http://forum.ustmb.ir/usertag.php?do=list&action=hash&hash=%22%29]#")[/URL]
    Console.Write( "\n\t\t\t By Seyyed Hossein Hasan Pour\n");

    Dijkstra();

    Console.ReadKey();
    }

    static void Dijkstra()
    {
    int Binahayat = 999999;
    int[] Distance = new int[20];
    int[,] Matrice_wazn = new int[20,20];
    int nazdiktarin_node_peymayesh_nashode = -9999;//in nazdiktarin node peymayesh nashode hast ke ma mikhonimesh
    bool[] Peymayesh_shode = new bool[20];
    int tedade_nodeha;

    //daryafte vazne yalha
    Console.Write("\nLotfan Tedade Nodha ra vared konid ");
    tedade_nodeha = int.Parse(Console.ReadLine());
    Console.Write("\nHala node shoro ra vared konid ");
    node_shoro = int.Parse(Console.ReadLine());
    node_shoro--;

    Console.Write("\nLotfan Hala be tartip vazne har yal ra vared konid :");
    for(int satr = 0; satr < tedade_nodeha; satr++)
    {
    Console.Write("\nSatr{0}\n",satr+1);
    for(int soton = 0; soton< tedade_nodeha; soton++)
    {
    Matrice_wazn[satr,soton] = int.Parse(Console.ReadLine());
    Console.Write("\n");
    }
    }


    //amade kardane arrayeha baraye shoroe karemon(avalin bar ke mikhaeem shoro konim hich ja ro nemitonim bebinim,harfe ostad sare class o be yad biarin.
    for(int shomare_node = 0; shomare_node < tedade_nodeha; shomare_node++)
    {
    Peymayesh_shode[shomare_node] = false;
    Distance[shomare_node] = Binahayat;
    Node_ghabli[shomare_node] = -1;
    }
    Distance[node_shoro] = 0;
    // badane asli dijkstra
    //int Minimum = Binahayat;
    for(int shomarande = 0; shomarande < tedade_nodeha; shomarande++)
    {

    //int nazdiktarin_node_peymayesh_nashode = Nazdiktarin_Node_Peymayesh_Nashode();
    //deghat kardin ke chera in karo kardam , man mitonestam ye tabe dorost konam ,ama
    //baraye raho neshon bedam , haminjori aval az bala shoro kardam be ghadam be ghadam peyadesazi
    //hala jelotar version dovom ro mibinim ba ham ke vaghty az tavabe estefade mikonim cheghadr code khoshkel tar mishe va rahat tar mishe tamarkoz kard o khond
    {
    int Minimum = Binahayat;
    for(int i = 0; i < tedade_nodeha; i++)
    {
    if( (Peymayesh_shode[i] == false) && (Minimum > Distance[i]) )
    {
    Minimum = Distance[i];
    nazdiktarin_node_peymayesh_nashode = i;
    }
    }
    }
    Peymayesh_shode[nazdiktarin_node_peymayesh_nashode] = true;

    for(int i = 0; i < tedade_nodeha; i++)
    {
    if((Peymayesh_shode[i] == false) && (Matrice_wazn[nazdiktarin_node_peymayesh_nashode,i] > 0))
    {
    if(Distance[i] > Distance[nazdiktarin_node_peymayesh_nashode] + Matrice_wazn[nazdiktarin_node_peymayesh_nashode,i])
    {
    Distance[i] = Distance[nazdiktarin_node_peymayesh_nashode] + Matrice_wazn[nazdiktarin_node_peymayesh_nashode,i];
    Node_ghabli[i] = nazdiktarin_node_peymayesh_nashode;
    }
    }
    }
    }
    //chape masir
    for(int i = 0; i < tedade_nodeha; i++)
    {
    if(i == node_shoro)
    {
    Console.Write("{0}--{1}",node_shoro+1,node_shoro+1);
    }
    else
    {
    chape_masir_baraye(i);
    }
    Console.Write("->{0}\n",Distance[i]);
    }


    }
    static void chape_masir_baraye(int node)
    {
    if (node == node_shoro)
    {
    Console.Write("{0}--", node_shoro+1);
    }
    else if (Node_ghabli[node] == -1)
    {
    Console.Write("\nMasiri vojod nadarad! \n");
    }
    else
    {
    chape_masir_baraye(Node_ghabli[node]);
    Console.Write("{0}--",node+1);
    }
    }

    }
    }





    فایل های پیوست شده
    Tishab, siryahya و pashekosh این نویسه را میپسندند.
    توکل بخدا
    http://DeepLearning.ir
    اولین و تنها مرجع یادگیری عمیق ایران


    هرکس از ظن خود شد یار من
    از درون من نجست اسرار من




  3. #3
    عضو تازه وارد
    تاریخ عضویت
    2012 May
    محل سکونت
    tabriz
    ارسال ها
    1
    تشکر
    2
    تشکر شده 0 بار در 0 پست


    آيا اين پست براي شما سودمند بود؟ بله | خیر
    الگوی خوب و کاربردی بود
    ممنون از لطفتون

    pashekosh این نویسه را میپسندد.

  4. #4
    عضو تازه وارد
    تاریخ عضویت
    2013 December
    ارسال ها
    1
    تشکر
    0
    تشکر شده 0 بار در 0 پست


    آيا اين پست براي شما سودمند بود؟ بله | خیر
    درود بر شما
    بنده می خوام این بخش فایل های الگوریتم دایجسترا دانلود کنم ولی اجازه دانلود ندارم اگر لطف کنید برام ارسال کنید یا اکانت بنده رو کاری کنید که بتونم دانلود کنم کنید ممنون میشم.


 

 

کاربران برچسب خورده در این موضوع

علاقه مندی ها (Bookmarks)

علاقه مندی ها (Bookmarks)

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

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


Powered by vBulletin
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO 3.6.0
Persian Language By Ustmb.ir
این انجمن کاملا مستقل بوده و هیچ ارتباطی با دانشگاه علوم و فنون مازندران و مسئولان آن ندارد..این انجمن و تمامی محتوای تولید شده در آن توسط دانشجویان فعلی و فارغ التحصیل ادوار گذشته این دانشگاه برای استفاده دانشجویان جدید این دانشگاه و جامعه دانشگاهی کشور فراهم شده است.لطفا برای اطلاعات بیشتر در رابطه با ماهیت انجمن با مدیریت انجمن ارتباط برقرار کنید
ساعت 03:12 AM بر حسب GMT +4 می باشد.