نحوه پیاده سازی الگوریتم در پروژه :

ابتدا برای ایجاد گره در مکان دلخواه دوبار کلیک کنید تا گره مورد نظر ایجاد شود سپس برای ایجاد یال یا همان ارتباط بین گره ها 

ابتدا روی گره اول کلیک کنید سپس روی گره دوم که میخواهید با آن ارتباط داشته باشد کلیک کنید تا بین آنها ارتباط ایجاد شود.

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

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

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

• مجموعه‌ی DD که اعضای آن به صورت didi نمایش داده شده و بیانگر کوتاهترین مسیر از مبدأ به گره vivi در پایان هر تکرار الگوریتم است. این مقادیر در ابتدا به ازای تمامی گره‌ها برابر ∞∞ است.
• مجموعه‌ی PP که اعضای آن به صورت pipi نمایش داده شده و در پایان هر تکرار گره پیشین گره vivi را که گره مبدأ از طریق آن به این گره در کوتاهترین مسیر دسترسی دارد، مشخص می‌کند. این مقادیر در ابتدا برای هیچ‌کدام از گره‌ها تعریف شده نبوده و در تکرارهای آن مقداردهی می‌شوند.
• مجموعه‌ی UU که اعضای آن گره‌های بررسی نشده در الگوریتم است. این مجموعه در ابتدا شامل تمامی گره‌های گراف است.

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

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

2- به ازای هر یال خروجی از گره جاری (vjvj) به یک گره از مجموعه‌ی UU مانند vkvk مقدار dj+ejkdj+ejk را محاسبه کرده و اگر مقدار آن از dkdk کوچکتر باشد، جایگزین کن. منظور از ejkejk اندازه‌ی یال از گره vjvj به vkvk است. در صورت جایگزین شدن مقدار جدید، مقدار pkpk نیز برابر با گره vjvj می‌شود.

3- از مجموعه گره‌های عضو UU گره با کوچکترین dd (غیر ∞∞) را به عنوان گره جاری انتخاب و از مجموعه‌ی UU‌ حذف کن.

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

5- مقدار didi برای گره vivi‌ کوتاهترین مسیر از مبدأ به آن گره را مشخص کرده است که از طریق گره pipi برای گره مبدأ در دسترس است.

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

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

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

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

نکته: در مرحله‌ی سوم اگر مقدار تمامی didi–ها برای گره‌های موجود در UU برابر ∞∞ باشد، به معنای آن است که هیچ مسیری از مبدأ به آن گره‌ها وجود ندارد و اجرای الگوریتم با مشخص شدن مسیرهای ممکن به سایر گره‌ها خاتمه پیدا می‌کند. در مورد گراف‌های بدون جهت می‌توان نتیجه گرفت که چنین گرافی ناهمبند است. اما در مورد گراف جهت‌دار لزوما اینگونه نیست و تنها می‌توان ادعا داشت که قویا همبند نیست. به عنوان مثال در گراف همبند زیر مسیری از گره 1 به گره 5 وجود ندارد:

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