الگوریتم دایکسترا - الگوریتمستان
الگوریتمستان
1914.585.00
  »  

       

آشنایی با الگوریتم دایکسترا برای یافتن کوتاهترین مسیر تک‌مبدأ در گراف وزن‌دار بدون یال منفی با قطعه کد به زبان ++C

الگوریتم دایکسترا (دیکسترا، دایجسترا - Dijkstra) یک راهکار حریصانه برای یافتن کوتاهترین مسیر از مقصد ثابت (تک منبع) به سایر گره‌های گراف وزن‌دار است. این گراف می‌تواند معرف مسیرهای یک شهر و تقاطع‌های آن باشد که انبار شرکت در یک گره آن قرار داشته و هدف یافتن کوتاهترین مسیر به هر محل دیگر از این انبار است. طبیعتا این الگوریتم در یافتن کوتاهترین مسیر بین دو گره مشخص نیز کاربرد دارد. تنها شرط لازم برای استفاده از این الگوریتم نامنفی بودن وزن یال‌های گراف است.

    الگوریتم دایکسترا به صورت حریصانه عمل کرده و در تکرارهای متوالی طول کوتاهترین مسیر از مبدأ به یکی از گره‌های گراف را به دست می‌آورد. در این الگوریتم از سه مجموعه استفاده می‌شود:

  • مجموعه‌ی $D$ که اعضای آن به صورت $d_i $ نمایش داده شده و بیانگر کوتاهترین مسیر از مبدأ به گره $v_i$ در پایان هر تکرار الگوریتم است. این مقادیر در ابتدا به ازای تمامی گره‌ها برابر $\infty$ است.
  • مجموعه‌ی $P$ که اعضای آن به صورت $p_i$ نمایش داده شده و در پایان هر تکرار گره پیشین گره $v_i$ را که گره مبدأ از طریق آن به این گره در کوتاهترین مسیر دسترسی دارد، مشخص می‌کند. این مقادیر در ابتدا برای هیچ‌کدام از گره‌ها تعریف شده نبوده و در تکرارهای آن مقداردهی می‌شوند.
  • مجموعه‌ی $U$ که اعضای آن گره‌های بررسی نشده در الگوریتم است. این مجموعه در ابتدا شامل تمامی گره‌های گراف است.

    مراحل الگوریتم دایکسترا برای یافتن کوتاهترین مسیر از گره $v_0$ به سایر گره‌ها به این شرح است:

    1- گره $v_0$ را به عنوان گره جاری از $U$‌ حذف کرده، مقدار $d_0$ را برابر صفر قرار داده و مراحل 2 تا 4 را تکرار کن.

    2- به ازای هر یال خروجی از گره جاری ($v_j$) به یک گره از مجموعه‌ی $U$ مانند $v_k$ مقدار $d_j + e_{jk}$ را محاسبه کرده و اگر مقدار آن از $d_k$ کوچکتر باشد، جایگزین کن. منظور از $e_{jk}$ اندازه‌ی یال از گره $v_j$ به $v_k$ است. در صورت جایگزین شدن مقدار جدید، مقدار $p_k$ نیز برابر با گره $v_j$ می‌شود.

    3- از مجموعه گره‌های عضو $U$ گره با کوچکترین $d$ (غیر $\infty$) را به عنوان گره جاری انتخاب و از مجموعه‌ی $U$‌ حذف کن.

    4- اگر $U$‌ تهی است یا در مرحله‌ی 3 هیچ گرهی برای انتخاب به عنوان گره جاری جدید وجود نداشت، برو به مرحله‌ی 5.

    5- مقدار $d_i$ برای گره $v_i$‌ کوتاهترین مسیر از مبدأ به آن گره را مشخص کرده است که از طریق گره $p_i$ برای گره مبدأ در دسترس است.

    به عنوان مثال برای یافتن کوتاهترین مسیر از گره شماره‌ی 1 به سایر گره‌ها در گراف زیر:

      

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

      

    ابتدا گره‌های مجاور گره شماره‌ی 1 بررسی شده:

      

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

      

    و گره با کمترین $d$ انتخاب می‌شود:

      

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

      

    و به همین ترتیب الگوریتم تا انتخاب تمامی گره‌ها پیش می‌رود.

      

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

      

    نکته: در مرحله‌ی سوم اگر مقدار تمامی $d_i$-ها برای گره‌های موجود در $U$ برابر $\infty$ باشد، به معنای آن است که هیچ مسیری از مبدأ به آن گره‌ها وجود ندارد و اجرای الگوریتم با مشخص شدن مسیرهای ممکن به سایر گره‌ها خاتمه پیدا می‌کند. در مورد گراف‌های بدون جهت می‌توان نتیجه گرفت که چنین گرافی ناهمبند است. اما در مورد گراف جهت‌دار لزوما اینگونه نیست و تنها می‌توان ادعا داشت که قویا همبند نیست. به عنوان مثال در گراف همبند زیر مسیری از گره 1 به گره 5 وجود ندارد:

      

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

      

    نکته: خروجی الگوریتم دایکسترا یک درخت است که گره مبدأ در ریشه قرار دارد. اگر گراف همبند باشد، درخت تولید شده یک درخت پوشا خواهد بود. در مورد گراف‌های ناهمبند نیز درخت پوشای هر مؤلفه‌ی همبندی تولید می‌شود. در حالت کلی چنین درختی لزوما درخت پوشای کمینه نیست. به عنوان مثال در گراف زیر، درخت تولید شده توسط الگوریتم دایکسترا با شروع از گره شماره‌ی 1 نمی‌تواند یک درخت پوشای کمینه برای گراف باشد:

      

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

      

پیاده‌سازی الگوریتم دایکسترا در زبان ++C

  [بازگشت به فهرست]

یک پیاده‌سازی ساده برای الگوریتم دایکسترا با ساده‌ترین ابزارهای زبان برنامه‌نویسی ++C به این ترتیب است:

      

void dijkstra(int adjacencyMatrix[MAX][MAX], int p[MAX], int numberOfNodes, int sourceNode){
  int d[MAX], currentNode;
  bool u[MAX];
  for(int i = 0 ; i < numberOfNodes ; i++){
    d[i] = INT_MAX;
    u[i] = true;
    p[i] = -1;
  }
  currentNode = sourceNode;
10   d[currentNode] = 0;
11   u[currentNode] = false;
12   while(true){
13     int minCost = INT_MAX, minNode = -1;
14     for(int i = 0 ; i < numberOfNodes ; i++)
15       if(u[i] && adjacencyMatrix[currentNode][i] != INT_MAX && d[currentNode] + adjacencyMatrix[currentNode][i] < d[i]){
16         p[i] = currentNode;
17         d[i] = d[currentNode] + adjacencyMatrix[currentNode][i];
18       }
19     for(int i = 0 ; i < numberOfNodes ; i++)
20       if(u[i] && d[i] < minCost)
21       {
22         minCost = d[i];
23         minNode = i;
24       }
25     if(minNode == -1)
26       break;
27     u[minNode] = false;
28     currentNode = minNode;
29   }
30 }

  

پيچيدگي و مرتبه‌ی زمانی الگوریتم دایکسترا

  [بازگشت به فهرست]

در قطعه کد ساده‌ی فوق در هر تکرار حلقه‌ی while یک سطر از ماتریس مجاورت به طور کامل پیمایش می‌شود. تعداد تکرار حلقه‌ی while نیز در بدترین حالت برابر تعداد گره‌های گراف است. در نتیجه این کد در مرتبه‌ی زمانی $ O(n^2)$ اجرا می‌شود. در حالت کلی برای گراف وزن‌دار $G = (V, E)$ تعداد یال‌های مورد نیاز برای بررسی از مرتبه‌ی $\vert E \vert $ (تعداد اعضای مجموعه‌ی $E$) است که یک حد پایین برای مرتبه‌ی زمانی اجرای الگوریتم‌ها را نشان می‌دهد. این مرتبه در یک گراف کامل یا نسبتا پر همان مرتبه‌ی $O(n^2)$ است. تا کنون راهکارهای متعددی برای کاهش عملیات یا حافظه‌ی مصرفی ارائه شده است؛ اما به طور طبیعی عملکرد همگی آنها ارتباط مستقیم با تعداد یال‌های گراف دارند که در حالت کلی از مرتبه‌ی $O(n^2)$ است.

    نکته: اگر هدف از اجرای الگوریتم دایکسترا یافتن کوتاهترین به یک گره مشخص باشد، کافی است در قطعه کد فوق شرطی برای بررسی برابر بودن currentNode با گره مذکور به انتهای حلقه‌ی while اضافه شود.

    توجه: در الگوریتم دایکسترا فرض بر آن است که اضافه شدن یک یال به مسیر باعث افزایش طول آن خواهد شد. بر همین مبنا به صورت حریصانه کوتاهترین مسیر موجود انتخاب می‌شود. بنابراین اگر گراف یال منفی داشته باشد، این الگوریتم لزوما به درستی عمل نخواهد کرد. به عنوان مثال در گراف زیر:

      

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

      

    در اولین مرحله‌ی الگوریتم برای یافتن کوتاهترین مسیرها از گره شماره‌ی 1، دو یال با طول‌های 6 و 3 بررسی شده و یال به طول 3 به خاطر طول کمتر نسبت به یال دیگر انتخاب می‌شود. در حالی که مسیر عبوری از گره 2 به سمت گره 3 طول کوتاهتر 1 را دارد.

    نکته: برای محاسبه‌ی کوتاهترین مسیر تک منبع در گراف‌های وزن‌دار با وزن منفی از الگوریتم بلمن-فورد استفاده می‌شود.


این نوشته آخرین بار در تاریخ شنبه، ۱ خرداد ماه ۱۳۹۵ مورد بازنویسی نگارشی قرار گرفته است.

این نوشته آخرین بار در تاریخ مورد بازنویسی علمی قرار گرفته است.
نوشته‌های مرتبط
        ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
        آشنایی با الگوریتم فلوید-وارشال برای یافتن کوتاهترین مسیرهای گراف با قطعه کد نمونه به زبان برنامه‌نویسی ++C
        بررسی مسئله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی موجود در کتاب Programming Challenges و وبسایت UVa Online Judge
        بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه‌ی آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
        معرفی الگوریتم جستجوی اول عمق (DFS) برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C
        بررسی مسئله‌ی آسانسورها (Elevators)، از سوالات مسابقات برنامه‌نویسی ACM
        بررسی مسئله‌ی بشکه‌های آب (Water Barrels)، از سوالات مسابقات برنامه‌نویسی بیان
        معرفی الگوریتم جستجوی اول سطح (BFS) برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C
        بررسی مسئله‌ی تاریخچه‌ی جدول (Grid History)، از سوالات مسابقات برنامه‌نویسی بیان
        آشنایی با روش حریصانه و کاربردهای آن مانند مسئله‌ی خرد کردن پول
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

 


» سبحان

یکشنبه، ۱۷ اسفند ماه ۱۳۹۳، ساعت ۱۸:۵۰
سلام
خیلی وقت بود پستی نمیذاشتین!!
09



چهارشنبه، ۲۰ اسفند ماه ۱۳۹۳، ساعت ۲۳:۵۴
مسعود:
بله درسته. در تلاشم به این امور نظم بدم.
ممنون از توجهتون. 01

» hadi

یکشنبه، ۷ تیر ماه ۱۳۹۴، ساعت ۱۵:۴۰
با سلام خواهش مندم به این سوال پاسخ دهد؟؟؟؟؟؟

الگريتمي بنويسيد که بتواند اطلاعات يک گراف وزن دار را دريافت کند و کوتاهترين مسير بين 2 نود دلخواه را با استفاده از الگوريتم دايجسترا بدست آوريد

» پریسا

دوشنبه، ۱۷ خرداد ماه ۱۳۹۵، ساعت ۱۵:۱۰
مرسییییییییییی 060606

» سعید

یکشنبه، ۲۳ خرداد ماه ۱۳۹۵، ساعت ۱۹:۵۹
سلام وقت بخیر
الگوریتم های دایکسترا و آ-استار را بصورت گرافیکی پیاده سازی کرده ام که برای آموزش بهتر مفهوم هر دو الگوریتم و مقایسه با یکدیگر بسیار مفید می باشد.

دسترسی از طریق لینک های زیر:
http://saeedranjbar.ir/Dijkstra
http://saeedranjbar.ir/Astar


سه‌شنبه، ۲۵ خرداد ماه ۱۳۹۵، ساعت ۱۱:۰۱
مسعود:
ممنون دوست عزیز. 0101

» sara

یکشنبه، ۱۲ شهریور ماه ۱۳۹۶، ساعت ۱۲:۵۵
ممنون از مقالتون