کد الگوریتم دیکسترا همراه توضیحات و پیچیدگی زمانی

در نظریه گراف، الگوریتم دیکسترا (به انگلیسی: Dijkstra’s algorithm)‏ یکی از الگوریتم‌های پیمایش گراف است که توسط دانشمند هلندی علوم رایانه، اِدْسْخِر دِیْکْسْترا در سال ۱۹۵۹ ارایه شد.

روند الگوریتم دیکسترا مطابق زیر می باشد :

۱- انتخاب راس مبدا

۲- مجموعه ی S ، شامل رئوس گراف ، معین می شود. در شروع، این مجموعه تهی بوده و با پیشرفت الگوریتم، این مجموعه رئوسی که کوتاه ترین مسیر به آن ها یافت شده است را در بر می گیرد.

۳- راس مبدا با اندیس صفر را در داخل S قرار می دهد.

۴- برای رئوس خارج از S ، اندیسی معادل ، طول یال + اندیس راس قبلی ، در نظر می گیرد . اگر راس خارج از مجموعه دارای اندیس باشد، اندیس جدید کمترین مقدار از بین اندیس قبلی و طول یال + اندیس راس قبل ، می باشد.

۵- از رئوس خارج مجموعه، راسی با کمترین اندیس انتخاب شده و به مجموعه ی S اضافه می گردد.

۶- این کار را دوباره از مرحله ی ۴ ادامه داده تا راس مقصد وارد مجموعه ی S شود.

در پایان اگر راس مقصد دارای اندیس باشد، اندیس آن نشان دهنده ی مسافت بین مبدا و مقصد می باشد. در غیر این صورت هیچ مسیری بین مبدا و مقصد موجود نمی‌باشد.

همچنین برای پیدا کردن مسیر می توان اندیس دیگری برای هر راس در نظر گرفت که نشان دهنده ی راس قبلی در مسیر طی شده باشد. بدین ترتیب پس از پایان اجرای الگوریتم، با دنبال کردن رئوس قبلی از مقصد به مبدا، کوتاه ترین مسیر بین دو نقطه نیز یافت می شود

  .

ر حین اجرای الگوریتم دو چیز به طور ضمنی نگهداری می‌شود. یکی مجموعهٔ از رأس‌هایی که وزن کوتاه‌ترین مسیر از مبدأ تا آن‌ها مشخص شده و دیگری دنبالهٔ که برای هر رأس ، مقدار برابر وزن کوتاه‌ترین مسیر از مبدأ تا است به شرطی که تمام رأس‌های این مسیر به جز از رئوس داخل باشند. در ابتدا تهی و مقادیر برای همهٔ رئوس به غیر از مبدأ بی‌نهایت است و مقدار آن برای مبدأ صفر گذاشته می‌شود. الگوریتم در هر مرحله رأسی خارج را که برای آن کمترین است انتخاب و به مجموعهٔ اضافه می‌کند و سپس مقادیر را برای رئوس همسایهٔ آن رأس به‌روز می‌نماید. در صورتی که نیاز به تشکیل درخت کوتاه‌ترین مسیر باشد، الگوریتم می‌بایست دنبالهٔ را که پدر رأس در درخت کوتاه‌ترین مسیر است، به همراه دنبالهٔ به‌روز کند.

پیچیدگی زمانی

در ساده‌ترین پیاده‌سازی الگوریتمِ دیکسترا، داده‌ها در آرایه یا لیست پیوندی ذخیره می‌شوند که بدین ترتیب مینیمم مقدار برای رئوس خارج با الگوریتمی خطی یافت می‌شود. در این حالت پیچیدگی زمانی خواهد بود، چراکه در گراف بدون جهت هر یال دقیقاً دوبار و در گراف جهت‌دار هر یال دقیقاً یک بار پیمایش می‌شود و هم‌چنین پیدا کردن مینیمم، زمان می‌خواهد که این مینیمم پیدا کردن بار تکرار خواهد شد. برای گراف‌های پراکنده (یعنی گراف‌هایی که خیلی کمتر از مجذور یال دارند) الگوریتم دیکسترا با نگهداری گراف در فهرست مجاورت و استفاده از صف اولویت‌دار (Priority-Queue) (برای پیدا کردن مینیمم) با پیچیدگی زمانی پیاده‌سازی می‌شود. در صورت استفاده از نگهدارندهٔ فیبوناتچی (Fibonacci heap) به جای صف اولویت‌دار، پیچیدگی زمانی با تحلیل جمعی (Amortized analysis) به بهبود می‌یابد.

کاربردها

ز جمله مهمترین کاربرد های این روش می توان به محاسبه ی کوتاه ترین فاصله ی دو نقطه در یک شهر از طریق راه های زمینی اشاره نمود. برای محاسبه ی کوتاه ترین مسیر بین دو نقطه باید نقاط مورد نظر در یک نقشه را علامت گذاری کرد و با استفاده از مشخصات نقاط(طول، عرض و ارتفاع) فاصله ی دو نقطه را در هر بار عملیات محاسبه نمود.توجه داریم که در ترافیک سرعت خودرو ها به شدت پایین آمده و این امر می تواند در انتخاب کوتاه ترین مسیر تاثیر گذار باشد چرا که ممکن است بین دو نقطه a,b راه های ۱و۲ موجود باشد که راه ۱ اتوبان و از خارج شهر و راه ۲ از داخل شهر عبور می کند. فرض کنید فاصله ی a,b از طریق راه ۱ حدود ۱۰ کیلومتر و از طریق راه ۲ حدود ۷ کیلومتر باشد ولی راه ۲ علی رقم فاصله ی کمتر دارای ترافیک سنگین است در نتیجه می توان انتظار داشت که در ساعات شلوغی استفاده از راه ۱ بهتر باشد.از آن جا که اساس محاسبات در این روش بر پایه ی فاصله بین دو نقطه است می توان کاهش سرعت را با افزایش فواصل هم ارز نمود چرا که اگر رابطه ی سرعت و فاصله را خطی در نظر بگیریم (D=V.T)تاثیر کاهش سرعت و افزایش مسافت یکسان است.از این رو لازم است تا ضرایب تعدیلی در فواصل بین نقاط ضرب شده و این مسائل را در محاسبات لحاظ کرد. از جمله مهم ترین این ضرایب می توان به ۳ مورد زیر اشاره نمود: ۱-ضریب ترافیک و شلوغی ۲-ضریب عرض معبر ۳-ضریب شیب که نشانگر افت سرعت در سر بالایی هااست. گرچه تعیین این ضرایب برای نقاط مختلف شهر نیازمند کارشناسان متخصص ترافیک و بررسی های آماری دقیق می باشد ولی می توان انتظار داشت که در اکثر موارد این ضرایب بین مقادیر ۱ تا ۲ بسته به شرایط تغییر کنند.

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

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

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

            }

        }

    }

}