الگوریتم دایجسترا Dijkstra در سی شارپ #C

در این بخش سورس کد پروژه الگوریتم دایجسترا Dijkstra در سی شارپ #C قرار داده شده است. الگوریتم دایجسترا Dijkstra یا دیکسترا یک راهکار حریصانه برای یافتن کوتاهترین مسیر از مقصد ثابت به سایر گره‌های گراف وزن‌دار است. این گراف می‌تواند معرف مسیرهای یک شهر و تقاطع‌های آن باشد که انبار شرکت در یک گره آن قرار داشته و هدف یافتن کوتاهترین مسیر به هر محل دیگر از این انبار است.

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

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

این الگوریتم برای پیدا کردن کوتاهترین مسیر بین گره‌ها کاربرد دارد. فرض کنید گرافی داریم که می‌خواهیم. کوتاهترین مسیر بین دو گره را در آن پیدا کنیم لازم به ذکر می‌باشد که الگوریتم دایجسترا شباهت زیادی به الگوریتم پریم دارد. در الگوریتم دایجسترا نیز درخت کوتاه‌ترین مسیر با استفاده از مبدا داده شده به عنوان ریشه، ساخته می‌شود.

در هر مرحله از الگوریتم، راسی پیدا می‌شود که در مجموعه دیگر مجموعه راس‌های در نظر گرفته نشده قرار دارد و دارای کمترین فاصله از ریشه است. در زیر نحوه اجرای الگورتیم دایجسترا کاملا توضیح داده شده است:

1. ساخت مجموعه sptSet مجموعه درخت کوتاه‌ترین مسیر  Shortest Path Tree Set که به دنبال راس‌های قرار گرفته در درخت کوتاه‌ترین مسیر می‌گردد.
2. تخصیص یک مقدار فاصله به همه راس‌ها در گراف ورودی.
3. تا هنگامی که sptSet شامل همه راس‌ها نشده است، اقدامات زیر انجام می‌شود: راس u انتخاب می‌شود که در sptSet نیست و دارای حداقل مقدار فاصله است. u در sptSet قرار می‌گیرد.
4. مقدار فاصله از همه راس‌های مجاور u به روز رسانی می‌شود.
5. برای به روز رسانی مقادیر فاصله، در همه راس‌های مجاور تکرار انجام می‌شود. برای هر راس مجاور v، اگر مجموع فاصله u از کد منبع و وزن یال u-v کمتر از مقدار فاصله v باشد، مقدار فاصله از v به روز رسانی می‌شود.

بررسی کد الگوریتم دایجسترا Dijkstra در سی شارپ #C

ساختار استفاده شده در برنامه به شرح زیر می‌باشند:

• GUI: اطلاعات را به صورت بصری نشان می‌دهد.
• RouteEngine: مسیر را محاسبه می‌کند و کوتاهترین مسیر را در اختیار شما قرار می‌دهد.
• کلاس Connection: این کلاس اطلاعات مربوط به اتصال بین دو گره را در خود جای داده است. که یک اتصال یک جهته از A به B را با یک وزن خاص متصل می‌کند.
• کلاس RouteEngine: این کلاس تمام مسیرها را از یک نقطه شروع مشخص محاسبه می‌کند.
• کلاس Route: این کلاس اطلاعات مربوط به مسیری را که بین دو نقطه (با کلاس RouteEngine تولید می شود) نگهداری می‌کند.

namespace Gui
{
    public class GuiLocation:Location
    {
       
        int x, y;
        bool selected;
        

        public int Width
        {
            get { return 25; }
            
        }

        public bool Selected
        {
            get { return selected; }
            set { selected = value; }
        }

        public int Y
        {
            get { return y; }
            set { y = value; }
        }

        public int X
        {
            get { return x; }
            set { x = value; }
}
}
}

تصویر خروجی برنامه

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

سورس کد الگوریتم دایجسترا Dijkstra در سی شارپ #C با استفاده از Microsoft Visual Studio 2013 نوشته شده است و دارای گزارش کار ۶ صفحه ای در Word است و بصورت کامل توسط گروه پشتیبانی پی استور تست و اجرا شده است و دارای نشان تضمین کیفیت پی استور می‌باشد. برای دانلود اثر مذکور آن را خریداری کنید.