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

[sinabed1393]

[font=BTitrBold,]الگوریتم دایکسترا
        آشنایی با الگوریتم دایکسترا برای یافتن کوتاهترین مسیر تک‌مبدأ در گراف وزن‌دار بدون یال منفی با قطعه کد به زبان ++C[/font]

آنچه در این نوشته می‌خوانید:
   •  الگوریتم دایکسترا
       »  پیاده‌سازی الگوریتم دایکسترا در زبان ++C
       »  پیچیدگی و مرتبه‌ی زمانی الگوریتم دایکسترا

الگوریتم دایکسترا[font=Times New Roman] (دیکسترا، دایجسترا - Dijkstra) یک راهکار حریصانه برای یافتن کوتاهترین مسیر از مقصد ثابت (تک منبع) به سایر گره‌های گراف وزن‌دار است. این گراف می‌تواند معرف مسیرهای یک شهر و تقاطع‌های آن باشد که انبار شرکت در یک گره آن قرار داشته و هدف یافتن کوتاهترین مسیر به هر محل دیگر از این انبار است. طبیعتا این الگوریتم در یافتن کوتاهترین مسیر بین دو گره مشخص نیز کاربرد دارد. تنها شرط لازم برای استفاده از این الگوریتم نامنفی بودن وزن یال‌های گراف است.
الگوریتم دایکسترا به صورت حریصانه عمل کرده و در تکرارهای متوالی طول کوتاهترین مسیر از مبدأ به یکی از گره‌های گراف را به دست می‌آورد. در این الگوریتم از سه مجموعه استفاده می‌شود:
[/font]
[list]
[*]مجموعه‌ی [font=MathJax_Math-italic]DD [/font]که اعضای آن به صورت [font=MathJax_Math-italic]didi [/font]نمایش داده شده و بیانگر کوتاهترین مسیر از مبدأ به گره [font=MathJax_Math-italic]vivi [/font]در پایان هر تکرار الگوریتم است. این مقادیر در ابتدا به ازای تمامی گره‌ها برابر [font=MathJax_Main]∞∞ [/font]است.
[*]مجموعه‌ی [font=MathJax_Math-italic]PP [/font]که اعضای آن به صورت [font=MathJax_Math-italic]pipi [/font]نمایش داده شده و در پایان هر تکرار گره پیشین گره [font=MathJax_Math-italic]vivi [/font]را که گره مبدأ از طریق آن به این گره در کوتاهترین مسیر دسترسی دارد، مشخص می‌کند. این مقادیر در ابتدا برای هیچ‌کدام از گره‌ها تعریف شده نبوده و در تکرارهای آن مقداردهی می‌شوند.
[*]مجموعه‌ی [font=MathJax_Math-italic]UU [/font]که اعضای آن گره‌های بررسی نشده در الگوریتم است. این مجموعه در ابتدا شامل تمامی گره‌های گراف است.
[/list][size=undefined]
مراحل الگوریتم دایکسترا برای یافتن کوتاهترین مسیر از گره [font=MathJax_Math-italic]v0v0 [/font]به سایر گره‌ها به این شرح است:
1- گره [font=MathJax_Math-italic]v0v0 [/font]را به عنوان گره جاری از [font=MathJax_Math-italic]UU[/font]‌ حذف کرده، مقدار [font=MathJax_Math-italic]d0d0 [/font]را برابر صفر قرار داده و مراحل 2 تا 4 را تکرار کن.
2- به ازای هر یال خروجی از گره جاری ([font=MathJax_Math-italic]vjvj) [/font]به یک گره از مجموعه‌ی [font=MathJax_Math-italic]UU [/font]مانند [font=MathJax_Math-italic]vkvk [/font]مقدار [font=MathJax_Math-italic]dj+ejkdj+ejk [/font]را محاسبه کرده و اگر مقدار آن از [font=MathJax_Math-italic]dkdk [/font]کوچکتر باشد، جایگزین کن. منظور از [font=MathJax_Math-italic]ejkejk [/font]اندازه‌ی یال از گره [font=MathJax_Math-italic]vjvj [/font]به [font=MathJax_Math-italic]vkvk [/font]است. در صورت جایگزین شدن مقدار جدید، مقدار [font=MathJax_Math-italic]pkpk [/font]نیز برابر با گره [font=MathJax_Math-italic]vjvj [/font]می‌شود.
3- از مجموعه گره‌های عضو [font=MathJax_Math-italic]UU [/font]گره با کوچکترین [font=MathJax_Math-italic]dd ([/font]غیر [font=MathJax_Main]∞∞) [/font]را به عنوان گره جاری انتخاب و از مجموعه‌ی [font=MathJax_Math-italic]UU[/font]‌ حذف کن.
4- اگر [font=MathJax_Math-italic]UU[/font]‌ تهی است یا در مرحله‌ی 3 هیچ گرهی برای انتخاب به عنوان گره جاری جدید وجود نداشت، برو به مرحله‌ی 5.
5- مقدار [font=MathJax_Math-italic]didi [/font]برای گره [font=MathJax_Math-italic]vivi[/font]‌ کوتاهترین مسیر از مبدأ به آن گره را مشخص کرده است که از طریق گره [font=MathJax_Math-italic]pipi [/font]برای گره مبدأ در دسترس است.
به عنوان مثال برای یافتن کوتاهترین مسیر از گره شماره‌ی 1 به سایر گره‌ها در گراف زیر:
  
[/size]

[size=undefined]
  
ابتدا گره‌های مجاور گره شماره‌ی 1 بررسی شده:
  
[/size]

[size=undefined]
  
و گره با کمترین [font=MathJax_Math-italic]dd [/font]انتخاب می‌شود:
  
[/size]

[size=undefined]
  
و به همین ترتیب الگوریتم تا انتخاب تمامی گره‌ها پیش می‌رود.
  
[/size]

[size=undefined]
  
نکته: در مرحله‌ی سوم اگر مقدار تمامی [font=MathJax_Math-italic]didi-[/font]ها برای گره‌های موجود در [font=MathJax_Math-italic]UU [/font]برابر [font=MathJax_Main]∞∞ [/font]باشد، به معنای آن است که هیچ مسیری از مبدأ به آن گره‌ها وجود ندارد و اجرای الگوریتم با مشخص شدن مسیرهای ممکن به سایر گره‌ها خاتمه پیدا می‌کند. در مورد گراف‌های بدون جهت می‌توان نتیجه گرفت که چنین گرافی ناهمبند است. اما در مورد گراف جهت‌دار لزوما اینگونه نیست و تنها می‌توان ادعا داشت که قویا همبند نیست. به عنوان مثال در گراف همبند زیر مسیری از گره 1 به گره 5 وجود ندارد:

  
[/size]

[size=undefined]
  
نکته[font=Times New Roman]:[/font] خروجی الگوریتم دایکسترا یک درخت است که گره مبدأ در ریشه قرار دارد. اگر گراف همبند باشد، درخت تولید شده یک درخت پوشا خواهد بود. در مورد گراف‌های ناهمبند نیز درخت پوشای هر مؤلفه‌ی همبندی تولید می‌شود. در حالت کلی چنین درختی لزوما درخت پوشای کمینه نیست. به عنوان مثال در گراف زیر، درخت تولید شده توسط الگوریتم دایکسترا با شروع از گره شماره‌ی 1 نمی‌تواند یک درخت پوشای کمینه برای گراف باشد:

  
[/size]

[size=undefined]
  
پیاده‌سازی الگوریتم دایکسترا در زبان[font=Times New Roman] ++C[/font]
  [بازگشت به فهرست]
یک پیاده‌سازی ساده برای الگوریتم دایکسترا با ساده‌ترین ابزارهای زبان برنامه‌نویسی ++C به این ترتیب است:
  
1 
void dijkstra(int adjacencyMatrix[MAX][MAX], int p[MAX], int numberOfNodes, int sourceNode){
2 
  int d[MAX], currentNode;
3 
  bool u[MAX];
4 
  for(int i = 0 ; i < numberOfNodes ; i++){
5 
    d[i] = INT_MAX / 2;
6 
    u[i] = true;
7 
    p[i] = -1;
8 
  }
9 
  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 نیز در بدترین حالت برابر تعداد گره‌های گراف است. در نتیجه این کد در مرتبه‌ی زمانی [font=MathJax_Math-italic]O(n2)O(n2) [/font]اجرا می‌شود. در حالت کلی برای گراف وزن‌دار [font=MathJax_Math-italic]G=(V,E)G=(V,E) [/font]تعداد یال‌های مورد نیاز برای بررسی از مرتبه‌ی [font=MathJax_Main]|E||E| ([/font]تعداد اعضای مجموعه‌ی [font=MathJax_Math-italic]EE) [/font]است که یک حد پایین برای مرتبه‌ی زمانی اجرای الگوریتم‌ها را نشان می‌دهد.این مرتبه در یک گراف کامل یا نسبتا پر همان مرتبه‌ی [font=MathJax_Math-italic]O(n2)O(n2) [/font]است. تا کنون راهکارهای متعددی برای کاهش عملیات یا حافظه‌ی مصرفی ارائه شده است؛ اما به طور طبیعی عملکرد همگی آنها ارتباط مستقیم با تعداد یال‌های گراف دارند که در حالت کلی از مرتبه‌ی [font=MathJax_Math-italic]O(n2)O(n2) [/font]است.
نکته: اگر هدف از اجرای الگوریتم دایکسترا یافتن کوتاهترین به یک گره مشخص باشد، کافی است در قطعه کد فوق شرطی برای بررسی برابر بودنcurrentNode با گره مذکور به انتهای حلقه‌ی while اضافه شود.

توجه[font=Times New Roman]:[/font] در الگوریتم دایکسترا فرض بر آن است که اضافه شدن یک یال به مسیر باعث افزایش طول آن خواهد شد. بر همین مبنا به صورت حریصانه کوتاهترین مسیر موجود انتخاب می‌شود. بنابراین اگر گراف یال منفی داشته باشد، این الگوریتم لزوما به درستی عمل نخواهد کرد. به عنوان مثال در گراف زیر:

  
[/size]

[size=undefined]
  
در اولین مرحله‌ی الگوریتم برای یافتن کوتاهترین مسیرها از گره شماره‌ی 1، دو یال با طول‌های 6 و 3 بررسی شده و یال به طول 3 به خاطر طول کمتر نسبت به یال دیگر انتخاب می‌شود. در حالی که مسیر عبوری از گره 2 به سمت گره 3 طول کوتاهتر 1 را دارد.
نکته[font=Times New Roman]:[/font] برای محاسبه‌ی کوتاهترین مسیر تک منبع در گراف‌های وزن‌دار با وزن منفی از الگوریتم بلمن-فورد استفاده می‌شود.[/size]