✤ الگوریتم دایجسترا

۱۵ اسفند ۱۳۹۳ الگوریتمی برای یافتن کوتاهترین مسیر تک‌مبدأ

الگوریتم حریصانه الگوریتم مسیریابی الگوریتم کوتاهترین مسیر پیمایش گراف الگوریتم الگوریتم دایکسترا الگوریتم گراف جستجوی اول سطح

الگوریتم دایکسترا (دیکسترا، دایجسترا - 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 / 2;

u[i] = true;

p[i] = -1;

}

currentNode = sourceNode;

d[currentNode] = 0;

u[currentNode] = false;

while(true){

int minCost = INT_MAX, minNode = -1;

for(int i = 0 ; i < numberOfNodes ; i++)

if(u[i] && adjacencyMatrix[currentNode][i] != INT_MAX && d[currentNode] + adjacencyMatrix[currentNode][i] < d[i]){

p[i] = currentNode;

d[i] = d[currentNode] + adjacencyMatrix[currentNode][i];

}

for(int i = 0 ; i < numberOfNodes ; i++)

if(u[i] && d[i] < minCost)

{

minCost = d[i];

minNode = i;

}

if(minNode == -1)

break;

u[minNode] = false;

currentNode = minNode;

}

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

[برگرد بالا]

در قطعه کد ساده فوق در هر تکرار حلقه 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 را دارد.

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