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

[Pouya]

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 است

//که کوتاه ترین مسیر درون آن قرار میگیرد.

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

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

• 32BIT الگوریتم استراسن در سی++ با توضیح خط به خط
• 16BIT حل مسئله ی 8 وزیر به زبان c++(بازگشتی و غیر بازگشتی)
• آموزش توضیحات مقدماتی بوت لودر دوم تدریس شده در کلاس استاد رحیم پور
• آموزش توضیحات مقدماتی بوت لودر اول تدرس شده در کلاس استاد رحیم پور
• الگوریتم ساده برای جمع بازگشتی در آرایه

[Hossein]

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

---

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

حالا نحوه کار با برنامه . خیلی ها سوالشون این بود که چرا ما وقتی تعداد نودها رو وارد میکنیم به اندازه تعداد نود سطر داریم ؟ اصلا یعنی چی ؟

تو شکل زیر توضیح دادم چرا . بینید وقتی شما گراف زیر رو میبینید . میبینید که مثلا 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 

اون صفری هم که میزاریم یعنی اینکه گره از خودش که فاصله ای نداره پس صفر میزاریم براش و همینطور الی اخر . تو شکل زیر اینو خیلی قشنگتر مشخص کردم .

مثالی رو هم که میبینید خانم اهنگر لطف کردند برای تست برنامه ارائه دادن و شما میتونید خروجی برنامه رو بسنجید و ببینید که آیا برنامه درست جواب میده یا نه .

496a45f4b2b957349979a9125d9bc3d04g.jpg

خوب الان فکر کنم مشخص شد که چرا ما به تعداد نودها از کاربر سطر دریافت میکنیم و اندازه میگیریم .

----------------------

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

//بسم الله الرحمن الرحیم 

//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);

            }

        }



    }

}

لینک مطلب اصلی در وبلاگ

نرم افزاری های دانشگاه علوم و فنون - ورژن نهایی الگوریتم دایجکسترا برای درس طراحی الگوریتم استاد حسامی فرد

[siryahya]

الگوی خوب و کاربردی بود
ممنون از لطفتون

[pashekosh]

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